🥚문제

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

• 다이나믹 프로그래밍
• 그래프 이론

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

N = int(input().strip())
# 입력받은 N*N 방을 벽(1)로 둘러싸게 (N+2)*(N+2) arr을 구성한다
arr = [[1]*(N+2)] + [[1] + list(map(int, input().split())) + [1]
                     for _ in range(N)] + [[1]*(N+2)]

# dp[r][c][0] = (r, c)까지 가로로 이동하는 방법의 수
# dp[r][c][1] = (r, c)까지 세로로 이동하는 방법의 수
# dp[r][c][2] = (r, c)까지 대각선으로 이동하는 방법의 수
dp = [[[0, 0, 0] for _ in range(N+2)] for __ in range(N+2)]

for r in range(1, N+1):
    for c in range(1, N+1):
        # 초기 파이프
        if (r, c) == (1, 2):
            dp[r][c] = [1, 0, 0]
            continue
        # 벽이면 skip
        if arr[r][c] == 1:
            continue
        # (r, c)까지 가로로 이동
        if 1 <= c-1 < N+1:
            dp[r][c][0] += dp[r][c-1][0]  # 이전 파이프 가로로 놓임
            dp[r][c][0] += dp[r][c-1][2]  # 이전 파이프 대각선으로 놓임
        # (r, c)까지 세로로 이동
        if 1 <= r-1 < N+1:
            dp[r][c][1] += dp[r-1][c][1]  # 이전 파이프 세로로 놓임
            dp[r][c][1] += dp[r-1][c][2]  # 이전 파이프 대각선으로 놓임
        # (r, c)까지 대각선으로 이동
        if 1 <= r-1 < N+1 and 1 <= c-1 < N+1:
            if arr[r][c-1] == 0 and arr[r-1][c] == 0:
                dp[r][c][2] += dp[r-1][c-1][0]  # 이전 파이프 가로로 놓임
                dp[r][c][2] += dp[r-1][c-1][1]  # 이전 파이프 세로로 놓임
                dp[r][c][2] += dp[r-1][c-1][2]  # 이전 파이프 대각선으로 놓임

print(sum(dp[N][N]))

---

🧂아이디어

DP

• 다이나믹 프로그래밍 기법으로 푼다. 이때, 파이프의 한 쪽 끝이 (r, c)에 도달했다면, 직전 위치에서 가로로 밀었을 때, 세로로 밀었을 때, 대각선으로 밀었을 때의 경우의 수를 나누어 생각한다.
  • dp[r][c][0] = 가로→로 밀어 (r, c)까지 도달하는 방법의 수
  • dp[r][c][1] = 세로↓로 밀어 (r, c)까지 도달하는 방법의 수
  • dp[r][c][2] = 대각선↘으로 밀어 (r, c)까지 도달하는 방법의 수

• dp[r][c]를 순회하며 값을 업데이트 해준다. (1 <= r < N+1, 1 <= c < N+1)

• 초기에 파이프는 (1, 1), (1, 2)를 가로방향으로 차지하고 있으므로
  dp[1][2] = [1, 0, 0]으로 초기화 해준다.

• arr[r][c] == 1 (벽) 이면 파이프를 밀 수 없으므로 skip한다.

• (r, c)까지 가로로 밀어 도달하기 위해서는
  • 이전 파이프가 가로 방향으로 놓여있거나, 대각선 방향으로 놓여있어야 한다.
  • dp[r][c][0] += dp[r][c-1][0],
    dp[r][c][0] += dp[r][c-1][2]

• (r, c)까지 세로로 밀어 도달하기 위해서는
  • 이전 파이프가 세로 방향으로 놓여있거나, 대각선 방향으로 놓여있어야 한다.
  • dp[r][c][1] += dp[r-1][c][1],
    dp[r][c][1] += dp[r-1][c][2]

• (r, c)까지 대각선으로 밀어 도달하기 위해서는
  • (r, c-1), (r-1, c)가 벽이 아니어야 하고 (arr[r][c-1] != 1 and arr[r-1][c] != 1)
  • 이전 파이프가 가로 방향으로 놓여있거나, 세로 방향으로 놓여있거나, 대각선 방향으로 놓여있어야 한다.
  • dp[r][c][2] += dp[r-1][c-1][0]
dp[r][c][2] += dp[r-1][c-1][1]
dp[r][c][2] += dp[r-1][c-1][2]

• 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 개수는 (N, N)까지 가로로 밀어 도달하는 방법, 세로로 밀어 도달하는 방법, 대각선으로 밀어 도달하는 방법의 합인 sum(dp[N][N])이다.