[백준] 17070번 파이프 옮기기 1 (by Python)

문제

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

 

풀이

    처음에는 직관적으로 생각나는 대로 다음과 같이 BFS로 풀었다.

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
q = deque()
q.append([(0, 0), (0, 1)])
ans = 0
if arr[-1][-1] == 1:
    print(0)
else:
    while q:
        left, right = q.popleft()
        next_left = right
        # 가로
        if left[0] == right[0]:
            steps = [(0, 1), (1, 1)]
        # 세로
        elif left[1] == right[1]:
            steps = [(1, 0), (1, 1)]
        # 대각선
        else:
            steps = [(1, 0), (0, 1), (1, 1)]
        for step in steps:
            next_right = (right[0] + step[0], right[1] + step[1])
            if next_right[0] < n and next_right[1] < n and arr[next_right[0]][next_right[1]] == 0:
                if all(step):
                    if arr[next_right[0] - 1][next_right[1]] == 0 and arr[next_right[0]][next_right[1] - 1] == 0:
                        if next_right[0] == (n - 1) and next_right[1] == (n - 1):
                            ans += 1
                        else:
                            q.append([next_left, next_right])
                elif next_right[0] == (n - 1) and next_right[1] == (n - 1):
                    ans += 1
                else:
                    q.append([next_left, next_right])
    print(ans)

    위와 같이 풀었을 때 두 가지 문제점이 있었는데, 첫 번째로는 무엇보다 시간 초과가 발생한다는 것이고 두 번째는 코드가 지저분하다는 점이었다. 현재 위치에서도 다음으로 갈 후보 위치에서도 가로 세로 대각선 모양에 따라 경우를 나눠야 하기 때문에 깔끔하게 코드를 짜기가 어려웠다. 그래서 '가로, 세로, 대각선을 효율적으로 관리할 수 있는 방법이 없을까?'라는 생각과 함께 브루트 포스 방법은 안되겠다고 생각했던 것 같다. 그 후에 다른 분의 풀이를 참고해서 나온 Dynamic Programming 방법을 차용한 코드는 다음과 같다.

 

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
# 0: 가로로 온 수 / 1: 세로로 온 수 / 2: 대각선으로 온 수
dp = [[[0] * n for _ in range(n)] for _ in range(3)]
dp[0][0][1] = 1
i = 2
while i < n:
    if arr[0][i]:
        break
    dp[0][0][i] = 1
    i += 1

for i in range(1, n):
    for j in range(2, n):
        if arr[i][j] == 0 and arr[i][j - 1] == 0 and arr[i - 1][j] == 0:
            dp[2][i][j] = sum(dp[k][i - 1][j - 1] for k in range(3))
        if arr[i][j] == 0:
            dp[0][i][j] = dp[0][i][j - 1] + dp[2][i][j - 1]
            dp[1][i][j] = dp[1][i - 1][j] + dp[2][i - 1][j]

print(sum(dp[i][-1][-1] for i in range(3)))

    이 풀이의 핵심은 DP로 맵을 구현하되, 가로 모양으로 도착했는지, 세로 모양으로 도착했는지, 대각선 모양으로 도착했는지에 따라 별도의 맵에 저장함으로써 이번 경로를 read하는 과정에서도 다음 경로에 write하는 과정에서도 코드가 복잡해지지 않고 오히려 효율적으로 해당 조건을 해결할 수 있다는 점이다. 

   평소 직관적인 풀이를 주로 하는 나로서는 놀라운 풀이법이었다.