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

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

17070번: 파이프 옮기기 1

스티커 문제를 발전 시킨다면 이 파이프 옮기기 문제가 될 것 같다.

좋은 DP 연습문제이다.

 

처음에는 당연히 BFS를 이용해서 풀어야겠다고 생각했는데,

BFS로는 최단경로를 찾아보기만 했지, 최단경로의 '개수'를 세어보진 않아서

백준님의 표현을 빌리자면, BFS의 형태를 모방한 브루트포스 풀이로 밖에 짜지지가 않았다.

(그리고 이 방식은 당연하게도 시간초과를 받는다..)

그래서 고민끝에 DP로 풀이를 변경했다.

 

이 문제는 결국 0,0 에서 n,n 방향으로 이동해야하고,

이동하는 과정도 위에서 아래로, 왼쪽에서 오른쪽으로 방향이다.

따라서 DP테이블을 그냥 2차원 배열을 정방향으로 순회하는 방향으로 채워나가면 된다.

 

이때 (a,b) 에서 파이프가 어떤 모양으로 놓여있었는지에 따라 다음에 어떻게 놓을 수 있는지 결정되므로

파이프가 놓여있던 모양을 구분해서 따로 DP테이블을 채워주면 된다.

형태만 놓고보면 3차원 테이블이 되지만,

2차원 테이블의 각 칸마다 3개의 데이터를 나눠서 저장한다고 이해하는게 더 잘 와닿을 것 같다.

---

import sys
input = sys.stdin.readline

HOR, CRO, VER = 0, 1, 2
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
dp = [[[0, 0, 0] for _ in range(n)] for _ in range(n)]
dp[0][1][HOR] = 1

for i in range(n):
    for j in range(n):
        if i == 0 and j == 0:
            continue
        if i+1 < n and board[i+1][j] == 0:
            dp[i+1][j][VER] += dp[i][j][VER]
            dp[i+1][j][VER] += dp[i][j][CRO]
        if j+1 < n and board[i][j+1] == 0:
            dp[i][j+1][HOR] += dp[i][j][HOR]
            dp[i][j+1][HOR] += dp[i][j][CRO]

        if i+1 < n and j+1 < n and board[i+1][j] == 0 and board[i][j+1] == 0 and board[i+1][j+1] == 0:
            dp[i+1][j+1][CRO] += dp[i][j][HOR]
            dp[i+1][j+1][CRO] += dp[i][j][CRO]
            dp[i+1][j+1][CRO] += dp[i][j][VER]

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

군대와서 새로 사용해보게된 코딩스타일인데, C의 상수를 쓰듯 대문자로 값을 정의해 배열에 써보니

코드가 좀 더 직관적으로 읽혀서 좋아졌다.

 

아무리 고민해도 이 문제를 그래프 탐색으로 푸는 방법은 잘 안떠오르는데,

좀 더 고민을 해봐야겠다.