[백준] 17070번 파이프 옮기기 1 [Python] - 다이나믹

 

 

아래 규칙에 의해서 NxN 격자판에서 $($1, 1$)$에서 $($N, N$)$으로 파이프를 연결하는 경우의 수를 구하는 문제,

불가능할 경우 0을 출력

처음에는 $($1, 1$)$, $($1, 2$)$에 걸친 파이프가 놓여있다.

 

가로

 

세로

 

대각선

 

파이프를 이동하려면 위 그림처럼

가로는 오른쪽,

세로는 아래,

대각선은 오른쪽, 아래, 오른쪽 아래에 아무것도 없어야 합니다.

 

격자 내에 벽이 존재할 수 있습니다.

 

문제

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 $(r, c)$로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

 

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

 

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

가로

 

세로

 

대각선

 

가장 처음에 파이프는 $(1, 1)$와 $(1, 2)$를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

입력

첫째 줄에 집의 크기 N$(3 ≤ N ≤ 16)$이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. $(1, 1)$과 $(1, 2)$는 항상 빈 칸이다.

출력

첫째 줄에 파이프의 한쪽 끝을 $(N, N)$으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다. 방법의 수는 항상 1,000,000보다 작거나 같다.

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

 

빈칸은 '0', 벽은 '1'로 주어짐

NxN 격자에 왼쪽, 오른쪽과 아래에 1로 벽을 세웁니다. 위에는 한 열을 추가합니다.

격자의 좌표를 $($0,0$)$에서 시작하는 게 아니라 $($1,1$)$에서 시작하도록 왼쪽과 위에 추가를 했고,

격자를 넘어가지 않도록 아래와 오른쪽에 벽을 추가했습니다.

 

파이프를 연결하는 방식이 가로, 세로, 대각선인지에 따라서 경우의 수를 저장할 dp를 생성합니다.

$($N, N$)$이 벽이거나, $($N, N-1$)$, $($N-1, N$)$이 둘 다 벽인 경우에는 불가능한 경우이므로 탐색을 하지 않고 0을 출력

 

처음에는 $($1, 2$)$에 초기값으로 가로에 1을 저장한다.

1행을 $($1, 3$)$부터 탐색하면서 벽이 아니면 왼쪽에 저장된 가로 값으로 업데이트 한다.

 

이후 격자를 탐색하면서 벽이 아는 곳에 대해서

가능한 모양의 파이프를 둘 수 있는 경우의 합을 업데이트해 나간다.

 

마지막으로 $($N, N$)$ 좌표의 가로, 세로, 대각선 경우의 수의 합을 출력한다.

 

import sys
input = sys.stdin.readline

N = int(input())
graph = [['1']]
dp = [[[0, 0, 0] for _ in range(N+1)] for _ in range(N+1)]

for _ in range(N):
    graph.append(['1']+input().rstrip().split()+['1'])
graph.append(['1']*(N+2))
if graph[N][N] == '1' or (graph[N-1][N] == '1' and graph[N][N-1] == '1'):
    print(0)
    exit()

dp[1][2][0] = 1
for c in range(3, N+1):
    if graph[1][c] == '0':
        dp[1][c][0] = dp[1][c-1][0]

for i in range(2, N+1):
    for j in range(3, N+1):
        if graph[i][j] == '0':
            if graph[i-1][j] == graph[i][j-1] == '0':
                dp[i][j][1] = sum(dp[i-1][j-1])
            dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][1]
            dp[i][j][2] = dp[i-1][j][2] + dp[i-1][j][1]
print(sum(dp[N][N]))

 

 

예제 입력 1 

3
0 0 0
0 0 0
0 0 0

예제 출력 1 

1

예제 입력 2 

4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

예제 출력 2 

3

예제 입력 3 

5
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

예제 출력 3 

0

예제 입력 4 

6
0 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

예제 출력 4 

13