[알고리즘/백준]17070 : 파이프 옮기기 1(python)

재귀를 이용하여 풀었다.
각 경우를 재귀로 구현하면 되는데
1. 가로
2. 세로
3. 대각선

가로로 갈 수 있는 건 가로, 대각선
세로로 갈 수 있는 건 세로, 대각선
대각선으로 갈 수 있는 건 가로, 세로, 대각선

각 경우의 좌표로 벽인지 아닌지 판단하고, 범위를 넘어가는지 체크 후 재귀를 실행하면 된다.

그림에 각 경우마다 비어있는 칸이 어디여야 하는지 나와있기 때문에 빈칸 체크도 함께 실행

def pipe(x, y, location):
    global ans
    if x == n - 1 and y == n - 1:  # 도착
        ans += 1
        return
    if location == 0 or location == 2:  # 가로로 갈 수 있는 경우
        if y + 1 < n and board[x][y + 1] == 0:
            pipe(x, y + 1, 0)
    if location == 1 or location == 2:  # 세로로 갈 수 있는 경우
        if x + 1 < n and board[x + 1][y] == 0:
            pipe(x + 1, y, 1)
    if x + 1 < n and y + 1 < n:
        if board[x + 1][y + 1] == 0 and board[x + 1][y] == 0 and board[x][y + 1] == 0:  # 대각선
            pipe(x + 1, y + 1, 2)


n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
ans = 0
if board[n - 1][n - 1] == 1:
    print(0)
else:
    pipe(0, 1, 0)
    print(ans)