[BOJ] 17070. 파이프 옮기기 1

백준 문제 주소:

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

문제 : 파이프를 주어진 NxN배열에서 (0,0) -> (N-1,N-1) 까지 옮길 수 있는 방법의 수를 구하라.

 

DP를 사용해서 푸는 문제였습니다.

처음엔 DFS로 풀었다가 14x14 배열까지는 답이 정상적으로 나오는데,

15x15 배열부터는 시간이 오래걸려서 시간초과가 뜹니다.

각 배열에 3차원의 DP를 사용하면 시간을 매우 단축하여 풀 수 있습니다.

※ dpdp() 함수 안의 2~35줄은 리팩토링으로 코드길이를 단축할 수 있습니다.

 

풀이 힌트 :

1. 파이프는 공간을 2개 차지하지만 (0,1)에 있는 파이프만 생각하면 된다.

2. 파이프의 이동경로는 딱 3가지 밖에 없다.

3. 대각선을 이동할 경우는 반대 대각선 두 배열에 1이 있는지 확인만 하면 된다.

4. dp로 만든 배열의 왼쪽 변과 밑 변만 dp를 계산하면 된다.

 

코드 : 

def dpdp(scale):
    for j in range(scale-1):
        for k in range(3):
            if dp[j][scale-2][k]:
                s = (j, scale-2, k)
                for i in range(3):
                    if s[2] - 1 <= i <= s[2] + 1:
                        rx = s[0] + dx[i]
                        ry = s[1] + dy[i]
                        if rx == scale or ry == scale:
                            continue
                        if board[rx][ry] == 1:
                            continue
                        if i == 1:
                            if board[rx-1][ry] == 1 or board[rx][ry-1] == 1 or board[rx-1][ry-1] == 1:
                                continue
                        if rx == scale-1 or ry == scale-1:
                            dp[rx][ry][i] += dp[j][scale-2][k]
    for j in range(2, scale-2):
        for k in range(3):
            if dp[scale-2][j][k]:
                s = (scale-2, j, k)
                for i in range(3):
                    if s[2] - 1 <= i <= s[2] + 1:
                        rx = s[0] + dx[i]
                        ry = s[1] + dy[i]
                        if rx == scale or ry == scale:
                            continue
                        if board[rx][ry] == 1:
                            continue
                        if i == 1:
                            if board[rx-1][ry] == 1 or board[rx][ry-1] == 1 or board[rx-1][ry-1] == 1:
                                continue
                        if rx == scale-1 or ry == scale-1:
                            dp[rx][ry][i] += dp[scale-2][j][k]
    for i in range(scale-1):
        if board[i+1][scale - 1] == 0:
            dp[i+1][scale - 1][0] += dp[i][scale - 1][1]
            dp[i+1][scale - 1][0] += dp[i][scale - 1][0]
        if board[scale - 1][i+1] == 0:
            dp[scale - 1][i+1][2] += dp[scale - 1][i][1]
            dp[scale - 1][i+1][2] += dp[scale - 1][i][2]

# 입력
N = int(input())
board = [list(map(int, input().split())) for i in range(N)]

# 초기값 설정
if board[N-1][N-1]:
    print(0)
else:
    dx = [1, 1, 0]
    dy = [0, 1, 1]
    dp = [[[0]*3 for i in range(N)] for j in range(N)]
    dp[0][1][2] = 1
    start = (0, 1, 2)
    for i in range(3, N + 1):
        dpdp(i)
    print(sum(dp[N-1][N-1]))