백준 17070 – 파이프 옮기기 1

#https://www.acmicpc.net/problem/17070
from sys import stdin

# N: 격자판의 크기 (N x N)
n = int(stdin.readline())
# maps: 격자판의 상태를 나타내는 2차원 리스트. 0은 빈 칸, 1은 벽
maps = [list(map(int, stdin.readline().split())) for i in range(n)]
# path: 파이프가 (N, N) 위치로 이동할 수 있는 방법의 총 수
path = 0

# dfs 함수: 파이프의 현재 위치와 상태를 기준으로 이동 가능한 경로를 탐색하는 함수
def dfs(i, j, rotation):
    global path, maps
    # 이동이 격자판 범위를 벗어나거나, 벽(1)을 만나면 탐색 중단
    if not(0 <= i < n) or not(0 <= j < n) or maps[i][j] == 1:
        return 
    # 대각선 이동 중 벽이 있으면 이동 불가, 탐색 중단
    if rotation == 2 and (maps[i-1][j] == 1 or maps[i][j-1] == 1):
        return
    # (N, N) 위치에 도달하면 경로 수 증가 후 탐색 중단
    if i == n-1 and j == n-1:
        path += 1
        return
    
    # 파이프가 가로 방향일 때: 오른쪽(가로) 또는 대각선으로 이동 가능
    if rotation == 0:
        dfs(i, j+1, 0) # 오른쪽으로 가로 이동
        dfs(i+1, j+1, 2) # 대각선으로 이동
    
    # 파이프가 세로 방향일 때: 아래(세로) 또는 대각선으로 이동 가능
    if rotation == 1:
        dfs(i+1, j, 1) # 아래로 세로 이동
        dfs(i+1, j+1, 2) # 대각선으로 이동
    
    # 파이프가 대각선 방향일 때: 모든 방향으로 이동 가능 (가로, 세로, 대각선)
    if rotation == 2:
        dfs(i, j+1, 0) # 오른쪽으로 가로 이동
        dfs(i+1, j, 1) # 아래로 세로 이동
        dfs(i+1, j+1, 2) # 대각선으로 이동

# N이 16이 아닌 경우에 대한 예외 처리입니다.
if n != 16:
    # 특정 조건에서는 경로가 존재하지 않으므로 0을 출력합니다.
    if (maps[0][2]==1 or (maps[n-1][n-2] == 1 and maps[n-2][n-1] == 1)):
        print(0)
    else:
        # DFS 탐색 시작점: 처음 파이프 위치(0, 1)와 방향(가로)
        dfs(0, 1, 0)
        # 최종 계산된 이동 경로의 수 출력
        print(path)
else:
    # N이 16인 경우, 동적 프로그래밍을 사용하여 문제를 해결합니다.
    dp = [[[0] * 3 for _ in range(n)] for _ in range(n)]
    dp[0][1][0] = 1  # 초기 조건 설정

    for r in range(n):
        for c in range(n):
            # 가로로 이동하는 경우의 수를 계산합니다.
            if c + 1 < n and maps[r][c + 1] == 0:
                dp[r][c + 1][0] += dp[r][c][0] + dp[r][c][2]
            
            # 세로로 이동하는 경우의 수를 계산합니다.
            if r + 1 < n and maps[r + 1][c] == 0:
                dp[r + 1][c][1] += dp[r][c][1] + dp[r][c][2]

            # 대각선으로 이동하는 경우의 수를 계산합니다.
            if r + 1 < n and c + 1 < n and maps[r + 1][c] == 0 and maps[r][c + 1] == 0 and maps[r + 1][c + 1] == 0:
                dp[r + 1][c + 1][2] += dp[r][c][0] + dp[r][c][1] + dp[r][c][2]

    # 최종적으로 (N, N)에 도달하는 모든 경우의 수를 합하여 출력합니다.
    print(sum(dp[n - 1][n - 1]))