✅ BOJ 17070 - 3차원 DP

시작 상태

처음 파이프는 (0,0)~(0,1)에 가로로 놓여 있다. 시작은 가로다. 그래서 dp[0][1][가로] = 1로 잡는다.

DP 배열 의미

dp[y][x][dir]는 (y,x)에 dir 방향으로 도착하는 경우의 수다.
dir은 0이 가로, 1이 세로, 2가 대각선.

이동 규칙

가로로 오면 가로나 대각선 갈 수 있음.
세로로 오면 세로나 대각선만 가능.
대각선으로 오면 가로, 세로, 대각선 전부 가능.

이동 조건

가로 이동은 오른쪽만 벽 아니면 됨.
세로 이동은 아래만 벽 아니면 됨.
대각선은 오른쪽, 아래, 대각선 방향 전부 벽 아니어야 함.

흐름

상태 돌면서 현재 칸 값이 0이면 건너뜀. 값 있으면 갈 수 있는 다음 칸에 더해줌.

종료 조건

dp[n-1][n-1]에 모인 가로, 세로, 대각선 전부 더해서 출력.

핵심

이런 DP는 어디서 왔는지 따질 필요 없음. 지금까지 온 값만 있으면 끝. 배열 만들고 돌면서 다음으로 넘기면 됨. 끝.

 

# dp
import sys
input=sys.stdin.readline
n=int(input())
graph=[list(map(int,input().split())) for _ in range(n)]
dp=[[[0]*3 for _ in range(n)] for _ in range(n)]
dp[0][1][0]=1
# dir=0,1,2(가로,세로,대각선)
for y in range(n):
    for x in range(n):
        for dir in range(3):
            if dp[y][x][dir]==0:
                continue
            #가로로 온 경우
            if dir==0 or dir==2:
                #가로 이동이 가능하면
                if x+1<n and graph[y][x+1]==0:
                    dp[y][x+1][0]+=dp[y][x][dir]
            #세로로 온 경우
            if dir==1 or dir==2:
                if y+1<n and graph[y+1][x]==0:
                    dp[y+1][x][1]+=dp[y][x][dir]
            #대각선으로 온 경우 (세 방향 모두 가능)
            if x+1<n and y+1<n:
                if graph[y][x+1]==0 and graph[y+1][x]==0 and graph[y+1][x+1]==0:
                    dp[y+1][x+1][2]+=dp[y][x][dir]
            
print(sum(dp[-1][-1]))