[백준] 17070 파이프 옮기기 1, python

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

처음에는 백트래킹으로 해결하려 했다가 시간초과가 났다.

 

→ 다음에는  →, ↘

↓ 다음에는   ↓, ↘

↘ 다음에는 →, ↘, ↓ 로 옮길 수 있다.

반대로

→이전에는   →, ↘ 

↓ 이전에는   ↓, ↘

↘ 이전에는   →, ↘, ↓ 만 가능하다.

 

→를 0, ↓를 1, ↘를 2라고 하고 dp [i][j]를 파이프의 오른쪽 끝의 위치가 i, j일 때 옮길 수 있는 경우의 수라고 하면

 

dp [i][j][현재방향] = sum(dp [현재방향에 따른 이전 파이프 위치][ 현재방향에 따른 이전 파이프 위치 ][이전방향]) 가 된다.

 

따라서 현재방향에 따라 3가지 경우로 나눈뒤에 dp를 갱신해 주면 된다.

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]

# 파이프의 오른쪽끝의 위치가 i,j일때의 경우의 수
dp = [[[0]*3 for _ in range(n)] for _ in range(n)]
dp[0][1][0] = 1

for i in range(n):
    for j in range(n):
        # →방향일 경우
        if j>0 and board[i][j] == 0:
            dp[i][j][0] += dp[i][j-1][0] +  dp[i][j-1][2] 

        # ↓방향일 경우
        if i>0 and board[i][j] == 0:
            dp[i][j][1] += dp[i-1][j][1] + dp[i-1][j][2]

        # ↘방향일 경우
        if i>0 and j>0 and board[i][j] == 0 and board[i-1][j] == 0 and board[i][j-1] == 0:
            dp[i][j][2] += dp[i-1][j-1][0] + dp[i-1][j-1][1] +dp[i-1][j-1][2]

print(sum(dp[n-1][n-1]))