처음에는 BFS로 풀었었다. 그러나 이러한 유형에 대해서는 BFS보다 DP로 푸는 것이 더 맞겠다는 생각을 하여 DP로 푸는 방법을 정리해보고자 한다.
혹시 BFS로 접근하는 방법이 궁금하다면 아래 링크를 참고 바란다.
[백준/Python] 17070. 파이프 옮기기 1 - BFS로 풀기
📄 문제
백준
난이도 : Gold 5
문제 제목 : 파이프 옮기기 1
✏️ 풀이 1
import sys
input = sys.stdin.readline
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
dp = [[[0] * 3 for _ in range(n)] for _ in range(n)]
# 초기값 정의하기
for i in range(1, n):
if board[0][i] == 1:
break
dp[0][i][0] = 1
for i in range(1, n):
for j in range(1, n):
if not board[i][j]:
dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2] # 가로
dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2] # 세로
if not (board[i][j] + board[i - 1][j] + board[i][j - 1]):
dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2] # 대각선
print(sum(dp[n - 1][n - 1]))✅ 풀이 한줄 설명:
DP로 풀 수 있는 문제이다. 위 풀이는 DP 테이블을 다음과 같이 정의한 풀이이다.
dp[i][j][k] = (i, j) 칸에 파이프를 k방향으로 가져오려 할 때, 가능한 모든 경우의 수 (단, k는 0, 1, 2)
✅ 풀이 자세한 설명:
DP 문제는 다음과 같이 풀이를 진행하는 것이 좋다.
- 테이블 정의하기
- 점화식 찾기
- 초기값 정의하기
🍎 1. 테이블 정의하기
dp[i][j][k] = (i, j) 칸에 파이프의 끝을 k방향으로 가져오려 할 때, 가능한 모든 경우의 수
(단, k는 0(가로), 1(세로), 2(대각선))
🍎 2. 점화식 찾기
- 가로로 가져올 때
dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2]
(i, j)칸에 파이프의 끝을 가로 방향으로 가져오려면,(i, j - 1)칸에 파이프의 끝이 가로로 놓여졌거나 대각선으로 놓여진 경우에만 가능하다. - 세로로 가져올 때
dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2]
(i, j)칸에 파이프의 끝을 세로 방향으로 가져오려면,(i - 1, j)칸에 파이프의 끝이 세로로 놓여졌거나 대각선으로 놓여진 경우에만 가능하다. - 대각선으로 가져올 때
dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2]
(i, j)칸에 파이프의 끝을 대각선 방향으로 가져오려면,(i - 1, j - 1)칸에 파이프의 끝이 *가로로 놓여졌거나, 세로로 놓여졌거나, 대각선**으로 놓여진 경우에 가능하다. 즉, 모든 경우에 가능하다.
➕ 점화식 계산을 위한 조건
항상 위의 점화식을 계산하면 되는 것이 아니다.
가로, 세로로 가져올 때는 해당 칸((i, j))이 벽이 아닌지 확인해야 한다.
대각선으로 가져올 때는 해당 칸과 위, 왼쪽 칸이 모두 벽이 아닌지 확인해야 한다.
🍎 3. 초기값 정의하기
dp[0][j] = 1(단,1 <= j < n)
board[0][j]가 1이 아닐때까지, 즉 벽을 만나기 전까지는dp[0][j] = 1이다.
첫번째 행은 처음에(0, 1)에 놓인 파이프를 오른쪽으로 쭉 가져오는 방법 밖에는 고려할 것이 없기 때문이다.dp[i][0] = 0(단,0 <= i < n)
처음에 파이프는(0, 1)에 가로로 놓여있기 때문에 첫번째 열은 파이프를 가져올 수가 없다.
📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '17070. 파이프 옮기기 1'
GitHub - [9강] BFS/응용문제 '17070. 파이프 옮기기 1'
✅ 비고
💫 목적지에 도달하는 모든 경우의 수를 구하는 문제면 DP가 더 효율적일 수 있다!
→ BFS는 예외처리 해줄 것이나 더 고려할 것이 많아진다. 잘 처리하지 않으면 시간초과가 날 확률이 높다.
