[백준 / 파이썬] 17070번: 파이프 옮기기 1

17070번: 파이프 옮기기 1

정답 코드

import sys
input = sys.stdin.readline

house_size = int(input())
house = [list(map(int, input().split())) for _ in range(house_size)]

dp = [[[0]*3 for _ in range(house_size+1)] for _ in range(house_size+1)]

dp[0][1][0] = 1

for r in range(house_size):
    for c in range(house_size):
        # 벽일경우
        if house[r][c] == 1:
            dp[r+1][c+1][2] = 0
            dp[r+1][c][1] = 0
            dp[r+1][c][2] = 0
            dp[r][c+1][0] = 0
            dp[r][c+1][2] = 0
            continue
        # 가로방향 = 가로방향, 대각선방향으로 왔을때
        dp[r][c+1][0] += dp[r][c][0] + dp[r][c][2]

        # 세로방향 = 세로방향, 대각선방향으로 왔을때
        dp[r+1][c][1] += dp[r][c][1] + dp[r][c][2]

        # 대각선방향 = 가로, 세로, 대각선 전부
        dp[r+1][c+1][2] += sum(dp[r][c])

print(sum(dp[house_size][house_size]))

문제 풀이

문제 풀이를 위해 다이나믹 프로그래밍(DP)을 사용합니다. DP는 작은 부분 문제들을 해결하여 큰 문제를 해결하는 기법으로, 이 문제에서는 각 구역까지의 경우의 수를 저장하는 DP 배열을 활용합니다.


우선, 입력을 받고 DP 배열을 초기화합니다. DP 배열의 크기는 (house_size + 1) × (house_size + 1) × 3으로 설정합니다. 이때, DP[i][j][k]는 i행 j열에 파이프의 형태가 k(0, 1, 2는 각각 가로, 세로, 대각선 방향을 의미)인 경우의 수를 저장합니다.


그리고 DP[0][1][0]을 1로 초기화합니다. 이는 출발점의 가장 왼쪽 위 칸에 파이프가 가로 방향으로 놓여진 경우의 수를 의미합니다.


이제 모든 구역을 순회하면서 경우의 수를 갱신해줍니다. 이때, 벽인 경우와 빈 공간인 경우를 구분하여 처리합니다.


만약 현재 구역이 벽인 경우, DP 배열의 해당 위치의 경우의 수를 0으로 갱신합니다. 이는 파이프를 놓을 수 없기 때문입니다.


그렇지 않은 경우에는 각 방향으로 파이프를 놓을 수 있는 경우의 수를 갱신합니다.

1. 가로 방향으로 파이프를 놓을 경우: DP[r][c+1][0] += DP[r][c][0] + DP[r][c][2]
   현재 위치에서 가로 방향으로 파이프를 놓기 위해서는 이전 위치에서 가로 방향이거나 대각선 방향으로 파이프가 놓여있어야 합니다. 따라서 DP[r][c+1][0]에 DP[r][c][0]과 DP[r][c][2]의 값을 더해줍니다.
2. 세로 방향으로 파이프를 놓을 경우: DP[r+1][c][1] += DP[r][c][1] + DP[r][c][2]
   현재 위치에서 세로 방향으로 파이프를 놓기 위해서는 이전 위치에서 세로 방향이거나 대각선 방향으로 파이프가 놓여있어야 합니다. 따라서 DP[r+1][c][1]에 DP[r][c][1]과 DP[r][c][2]의 값을 더해줍니다.
3. 대각선 방향으로 파이프를 놓을 경우: DP[r+1][c+1][2] += sum(DP[r][c])
   현재 위치에서 대각선 방향으로 파이프를 놓기 위해서는 이전 위치에서 가로, 세로, 대각선 방향에 파이프가 놓여있어야 합니다. 따라서 DP[r+1][c+1][2]에 DP[r][c]의 모든 값을 더해줍니다.

모든 구역을 순회한 후, DP[house_size][house_size]의 값을 모두 더하여 출력합니다. 이는 목적지에서 가로, 세로, 대각선 방향으로 파이프가 놓여진 경우의 수를 의미합니다.