[BOJ] 파이프 옮기기 1 (17070, G5)

문제 내용

 

 

풀이 과정

도착 상태가 가로인지, 세로인지, 대각선인지를 나눠서 모두 합쳐주면 된다. 

즉, 이를 기억하는 dp를 만들면 된다.

위의 7가지 이동 상황을 모두 각각을 점화식으로 만들면 되는데, 몇 가지 주의사항이 있다.

1. 맨 첫번째인  0행의 경우 가로줄 이동만 가능하다. 벽을 만나기 전까진 1, 벽을 만난 다음부터는 무조건 0
2. 두 번째 행부터는 세로, 대각선 이동도 가능하다.  단, 대각선은 0열, 1열에서는 움직일 수 없다. 파이프는 2칸이다.
3. 맨 첫번째 열은 그냥 경우가 0이다.

이를 바탕으로 최종 마지막 칸에서 가로 + 세로 + 대각선 하면 되는 문제.

import sys
input = sys.stdin.readline

# 가로로 도착하냐, 세로로 도착하냐, 대각선으로 도착하냐를 나눠서 계산
N = int(input())
maps = []
for _ in range(N):
    maps.append(list(map(int, input().split())))

dp = [[[0, 0, 0] for _ in range(N)] for _ in range(N)] # 가로, 세로, 대각선으로 나눠서 경우 계산

# 최초 파이프 세팅
dp[0][0][0] = 1
dp[0][1][0] = 1
for i in range(N):
    for j in range(N):
        # 첫 줄은 가로만 이동 가능.
        if i == 0:
            if j == 0 or j == 1:
                pass
            else:
                if maps[i][j] == 1:
                    dp[0][j][0] = 0
                else:
                    # 다시 위로 올라갈 수 없으므로, 0이면 0... 1이면 1.
                    dp[0][j][0] = dp [0][j-1][0]
        else:
            # 두번째 줄부터 처리
            # 만일 첫 번째 열일 경우, 문제가 된다.
            if j == 0:
                pass
            else:
                # 문제 이미지 대로.
                if maps[i][j] == 0:
                    dp[i][j][0] += dp[i][j-1][0]  # type 1 가로 -> 가로
                    dp[i][j][1] += dp[i-1][j][1]  # type 3 세로 -> 세로
                    dp[i][j][0] += dp[i][j-1][2]  # type 5 대각 -> 가로
                    dp[i][j][1] += dp[i-1][j][2]  # type 6 대각 -> 세로 
                # 대각선 이동 판단 칸.
                if j >= 2:
                    if maps[i][j] == 0 and maps[i][j-1] == 0 and maps[i-1][j] == 0:
                        dp[i][j][2] += dp[i-1][j-1][0] # type 2 가로 -> 대각
                        dp[i][j][2] += dp[i-1][j-1][1] # type 4 세로 -> 대각
                        dp[i][j][2] += dp[i-1][j-1][2] # type 7 대각 -> 대각
                     
print(sum(dp[-1][-1]))