[python] 백준 17070 파이프 옮기기 1

https://www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

문제 해결

• 파이프는 그래프에서 0좌표에만 놓을 수 있다. (1은 벽이므로)
• 파이프를 놓는 방법의 수는 이전 장소 (r,c) 좌표면 (r-1,c), (r,c-1), (r-1,c-1) 좌표의 영향을 받는다.
• 각 좌표에 어떻게 놓느냐에 따라 경우의 수가 달라진다. 문제의 그림을 참고하는 것이 좋다.
• DP를 3차원을 이용해서 풀면 충분히 쉽게 풀 수 있다.

 

CODE

n = int(input())
graph = [[] for _ in range(n)]

dp = [[[0]*n for _ in range(n)] for _ in range(3)]
# 3을 하는 이유는 그 좌표에서 가로 파이프인지 세로파이프인지 대각 파이프인지 종류를 분류하기 위하여(0가로, 1세로, 2 대각)
for i in range(n):
    graph[i] = list(map(int, input().split()))
dp[0][0][1] = 1 # 처음은 가로파이프로 연결하므로

for i in range(2,n):
    if graph[0][i] ==0:
        dp[0][0][i] = dp[0][0][i-1]

for r in range(1,n):
    for c in range(1,n):
        if graph[r][c] ==0 and graph[r][c-1]==0 and graph[r-1][c] ==0:
            # 현재 위치가 대각
            dp[2][r][c] = dp[0][r-1][c-1] +dp[1][r-1][c-1] + dp[2][r-1][c-1]
        if graph[r][c] ==0:
            # 현재 위치가 가로
            dp[0][r][c] = dp[0][r][c-1] + dp[2][r][c-1]
            # 현재 위치가 세로 파이프
            dp[1][r][c] = dp[1][r-1][c] + dp[2][r-1][c]
print(sum(dp[i][n-1][n-1] for i in range(3)))