[백준] 17070 - 파이프 옮기기 1 [Python(파이썬)]

문제

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

풀이

로봇 청소기와 점프를 합쳐 놓은 듯한 문제였다.

문제 유형은 다이나믹 프로그래밍이면서도, 구현 능력도 요구하는 문제였다.

문제에서 고려할 중요한 조건은 다음과 같다.

 

1) 가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다.

2) 파이프가 놓여진 방향에 따라 회전 방향이 결정된다.

3) 회전 방향에 따라 특정 칸이 무조건 비어있어야 한다.

 

directions에 각 방향 별로 회전할 수 있는 방향을 저장해둔다(가로: 0, 세로: 1, 대각선: 2)

cos에는 방향에 따른 좌표를 저장해둔다.

dp테이블은 3차원으로 구성했다. 3가지의 놓인 방향에 따른 경우의 수를 저장하기 위함이다.

또한, base case는 조건1)에 따라 dp[0][1][0] = 1이 된다.

 

3중 for문을 돌며 dp테이블에 접근하고 만약 dp[y][x][d] != 0이라면 check함수를 실행한다(d는 방향).

만약 dp[y][x][d] == 0이라면 해당 칸으로 이동시킬 방법이 없다는 것을 의미하기 때문이다.

 

check함수는 간단하다. 기본적인 그래프 탐색과 비슷하지만, 회전 방향이 대각선인지 여부에 따라 다르게 처리해줘야 한다. 만약 회전 방향이 가로/세로 방향이라면 한 칸만 비어있으면 된다(g[ny][nx] == 0).

하지만 회전 방향이 대각선이라면 두 칸이 더 비어있어야 한다(g[ny-1][nx] == 0 and g[ny][nx-1] == 0).

 

이 문제는 경로의 개수를 구하는 문제에서 움직이는 방향이 한정되어 있을 때, 동적계획법을 이용하여 빠른 시간에 문제를 해결할 수 있는 문제 유형이었다.

코드

import sys

def check(y, x, d):
    for direction in directions[d]:
        dy, dx = cos[direction]
        ny = y + dy
        nx = x + dx
        if 0 <= ny < n and 0 <= nx < n and not g[ny][nx]:
            if direction != 2: # 대각선이 아니면
                dp[ny][nx][direction] += dp[y][x][d]
            else: # 대각선이면
                if not g[ny-1][nx] and not g[ny][nx-1]:
                    dp[ny][nx][direction] += dp[y][x][d]

directions = {0: [0, 2], 1: [1, 2], 2: [0, 1, 2] } # 가로(0) / 세로(1) / 대각선(2)
cos = {0: [0, 1], 1: [1, 0], 2: [1, 1]} # (y, x)

n = int(sys.stdin.readline().strip())
dp = [[[0 for _ in range(3)] for _ in range(n)] for _ in range(n)]
g = []

for _ in range(n):
    g.append([int(x) for x in sys.stdin.readline().split()])

dp[0][1][0] = 1

for y in range(n):
    for x in range(n):
        for d in range(3):
            if dp[y][x][d] and not g[y][x]:
                check(y, x, d)        

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