백준 17070 파이프 옮기기

예상 대진표
https://programmers.co.kr/learn/courses/30/lessons/12985

처음에는 bfs로 해결하려 했지만 시간초과가 났다.
그래서 dfs인가 했지만 마찬가지로 시간초과였고, dp를 택하였다.

• 시간초과가 난 코드

from collections import deque
N = int(input())
direction = [((0,1),(1,1)), ((1,0),(1,1)), ((0,1),(1,0),(1,1))] ## 가로일때 세로일때 대각일때
graph = []
for _ in range(N):
    lst = list(map(int,input().split()))
    graph.append(lst)
## 현재상태
queue = deque([(0,1,0)])
answer = 0

while queue:
    x,y,i = queue.popleft()
    if x == N-1 and y == N-1:
        answer += 1
    for d in direction[i]:
        nx = x + d[0]
        ny = y + d[1]
        # print(nx,ny)
        if 0 <= nx < N and 0 <= ny < N:
            if d[0] == 1 and d[1] == 1:
                if graph[nx-1][ny] == 0 and graph[nx][ny] == 0 and graph[nx][ny-1] == 0:
                    queue.append((nx,ny,2))
            elif d[0] == 1 and d[1] == 0 and graph[nx][ny] == 0:
                queue.append((nx,ny,1))
            elif d[0] == 0 and d[1] == 1 and graph[nx][ny] == 0:
                queue.append((nx,ny,0))


print(answer)

• dp를 이용한 코드

n = int(input())
graph = []
for _ in range(n):
    lst = list(map(int,input().split()))
    graph.append(lst)

dp = [[[0]*n for i in range(n)] for i in range(n)]
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)))