[Python] 백준 17070: 파이프 옮기기 1

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

17070번: 파이프 옮기기 1

1. dp로 푸는 문제이다. (n, n) 좌표로 올수있는 방법은 대각선, 가로, 세로 총 3가지이다.

2. dy배열에 가로(0), 세로(1), 대각선(2)으로 올수있는방법 + 각 좌표의 방법으로 3차원배열을 만든다.

3. 가로 2가지, 세로 2가지, 대각선3가지 이고 대각선일때는 현재좌표와 (x-1, y), (x, y-1) 좌표가 벽으로 막혀있으면 안된다.

4. dfs를 돌려주면서 x나 y가 0보다 커야하고 벽으로 막혀있으면 안되며 좌표의 값이 존재하는경우 값을 반환해준다.

n = int(input())
dy = [[[0 for _ in range(3)] for _ in range(n)] for _ in range(n)]
pipe = [list(map(int, input().split())) for _ in range(n)]
dy[0][1][0] = 1

def dfs(x, y, z):
    if x < 0 or y < 0 or pipe[x][y]:
        return 0
    if dy[x][y][z]:
        return dy[x][y][z]
    if z == 0:
        dy[x][y][z] = dfs(x, y-1, 2) + dfs(x, y-1, 0)
    elif z == 1:
        dy[x][y][z] = dfs(x-1, y, 1) + dfs(x-1, y, 2)
    else:
        if 0 <= x-1 and 0 <= y-1 and pipe[x-1][y] == 0 and pipe[x][y-1] == 0:
            dy[x][y][z] = dfs(x-1, y-1, 0) + \
                dfs(x-1, y-1, 1) + dfs(x-1, y-1, 2)
    return dy[x][y][z]

dfs(n-1, n-1, 0), dfs(n-1, n-1, 1), dfs(n-1, n-1, 2)
print(sum(dy[n-1][n-1]))