[백준/Python] 17070. 파이프 옮기기 1 - BFS로 풀기

Choi Jimin·2024년 1월 31일

백준(BOJ)

목록 보기

27/28

이러한 유형에 대해 더 추천하는 풀이 방법을 발견해서 새로 포스팅을 작성하였다. 공부를 위해 현 포스팅을 읽어보는 것도 괜찮지만, 좀 더 일반적인 풀이를 담은 아래 포스팅을 추천한다.

[백준/Python] 17070. 파이프 옮기기 1 - DP로 풀기

이번 포스팅은 오답 풀이인 '✏️ 풀이 1'과 정답 풀이인 '✏️ 풀이 2' 로 2가지 코드가 정리되어있다.
정답 풀이만 보고 싶다면 '✏️ 풀이 2'를 참고하기 바란다.

📄 문제

백준
난이도 : Gold 5
문제 제목 : 파이프 옮기기 1

✏️ 풀이 1 / 오답 / 시간 초과

import sys
from collections import deque

input = sys.stdin.readline
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]

cnt = [0]
nxt = {0: {0: [(0, 1)], 2: ((0, 1), (1, 0), (1, 1))},  # 가로
       1: {1: [(1, 0)], 2: ((0, 1), (1, 0), (1, 1))},  # 세로
       2: {0: [(0, 1)], 1: [(1, 0)], 2: ((0, 1), (1, 0), (1, 1))}}  # 대각선
def bfs():
    deq = deque([(0, 1, 0)])  # (끝점 행, 끝점 열, 놓여있는 방향)

    while deq:
        y, x, d = deq.popleft()
        if y == N - 1 and x == N - 1:
            cnt[0] += 1
            continue

        for nxt_d, nxt_candi in nxt[d].items():
            # 모든 nxt_candi의 위치가 만족되어야 해당 위치를 deq에 추가
            flag = True
            for dy, dx in nxt_candi:
                ny = y + dy
                nx = x + dx
                if nx < 0 or ny < 0 or nx >= N or ny >= N:
                    flag = False
                    break
                if board[ny][nx] == 1:
                    flag = False
                    break
            if flag:
                deq.append((y + nxt_candi[-1][0], x + nxt_candi[-1][1], nxt_d))


bfs()
print(cnt[0])

✅ 풀이 한줄 설명:
현재 놓여진 방향에 따라 갈 수 있는 경우의 수가 달라지는 BFS 문제로 판단하여 푼 풀이이다.

✅ 풀이 자세한 설명:
일반적인 BFS와 달리 현재 칸에 파이프가 놓여진 방향에 따라 다음에 갈 수 있는 칸이 달라지는 문제이다.
또한, 끝 점에 도달하는 최소 횟수를 구하는 것이 아니라 모든 경우의 수를 구하는 문제이다.
따라서 아래의 사항들을 주의해 코드를 작성해야 한다.

현재 칸의 방향에 따라 다음에 갈 수 있는 칸이 달라진다.
다음에 갈 칸을 갈 수 있는지 확인할 때, 대각선의 경우 확인해야 할 칸이 다양하다.
끝점에 도달하는 모든 경우의 수를 구해야하기 때문에, visited를 따로 두지 않는다.

🍎 1. 현재 칸의 방향에 따라 다음에 갈 수 있는 칸이 달라진다.

현재 파이프가 놓여진 방향이

가로(0)면, 현재 좌표에
(0, 1)을 더한 가로(0)로,
(1, 1)을 더한 대각선(2)으로 갈 수 있다.
세로(1)면, 현재 좌표에
(1, 0)을 더한 세로(1)로,
(1, 1)을 더한 대각선(2)으로 갈 수 있다.
대각선(2)이면, 현재 좌표에
(0, 1)을 더한 가로(0)로,
(1, 0)을 더한 세로(1)로,
(1, 1)을 더한 대각선(2)으로 갈 수 있다.

🍎 2. 다음에 갈 칸을 갈 수 있는지 확인할 때, 대각선의 경우 확인해야 할 칸이 다양하다.

대각선으로 가려할 경우, 현재 위치에 (0, 1), (1, 0), (1, 1) 을 더한 칸들이 모두 비어있어야 갈 수 있다.

위의 '🍎 1~2번'을 고려해서, 다음과 같은 nxt 딕셔너리를 둔다.

nxt = {0: {0: [(0, 1)], 2: ((0, 1), (1, 0), (1, 1))},  # 가로
       1: {1: [(1, 0)], 2: ((0, 1), (1, 0), (1, 1))},  # 세로
       2: {0: [(0, 1)], 1: [(1, 0)], 2: ((0, 1), (1, 0), (1, 1))}}  # 대각선

즉, 현재 파이프의 방향이 0 이면, 다음에 nxt[0]의 key의 방향으로 갈 수 있는 것이고,
해당 key의 value 리스트(튜플) 칸들이 모두 비어져있어야 정말로 value의 마지막 위치(key의 방향에 따른 다음 위치)로 갈 수 있는 것이다.

이를 BFS 돌릴 때 다음과 같이 확인한다.

for nxt_d, nxt_candi in nxt[d].items():
	# 모든 nxt_candi의 위치가 만족되어야 해당 위치를 deq에 추가
	flag = True
	for dy, dx in nxt_candi:
		ny = y + dy
        nx = x + dx
        if nx < 0 or ny < 0 or nx >= N or ny >= N:
        	flag = False
            break
        if board[ny][nx] == 1:
            flag = False
            break
	if flag:
		deq.append((y + nxt_candi[-1][0], x + nxt_candi[-1][1], nxt_d))

🍎 3. 끝점에 도달하는 모든 경우의 수를 구해야하기 때문에, visited를 따로 두지 않는다.

끝점까지 가는 파이프 최소 움직임 횟수를 구하는 것이 아니기 때문에, 어떤 칸에 이전에 방문했다 하더라도 또 갈 수 있다.

🚫 오답 설명
해당 코드는 시간 초과로 오답을 반환한다.
이유는 '🍎 3. 끝점에 도달하는 모든 경우의 수를 구해야하기 때문에, visited를 따로 두지 않는다.' 때문이다.
다음과 같은 테스트케이스가 있을 때, 같은 칸에 대해서 굉장히 많은 반복이 일어날 수 있다.

16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

❗️ 해결 방법
queue 에 총 이동 거리가 짧은 순서대로 요소를 넣고 빼야 한다.
자세한 내용과 적용 방법은 밑의 '✏️ 풀이 2'를 참고바란다.

✏️ 풀이 2

import sys
import heapq

input = sys.stdin.readline

n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]

# 가장 안쪽 리스트의 인덱스는 방향 [가로:0,세로:1,대각선:2]
dist = [[[0] * 3 for _ in range(n)] for _ in range(n)]
dist[0][1][0] = 1 # (0, 1) 가로

pq = [] # priority_queue
heapq.heappush(pq, (1, (0, 1, 0))) # 우선순위: r + c, 즉 총 이동거리

while pq:
    p, (r, c, d) = heapq.heappop(pq)
    
    # 가로로 갈 수 있는 경우
    if d in (0, 2) and c + 1 < n and matrix[r][c + 1] == 0:
        if dist[r][c + 1][0] == 0:
            heapq.heappush(pq, (p + 1, (r, c + 1, 0)))
        dist[r][c + 1][0] += dist[r][c][d]
        
    # 세로로 갈 수 있는 경우
    if d in (1, 2) and r + 1 < n and matrix[r + 1][c] == 0:
        if dist[r + 1][c][1] == 0:
            heapq.heappush(pq, (p + 1, (r + 1, c, 1)))
        dist[r + 1][c][1] += dist[r][c][d]
        
    # 대각선으로 갈 수 있는 경우
    if r + 1 < n and c + 1 < n and matrix[r + 1][c] + matrix[r][c + 1] + matrix[r + 1][c + 1] == 0:
        if dist[r + 1][c + 1][2] == 0:
            heapq.heappush(pq, (p + 2, (r + 1, c + 1, 2)))
        dist[r + 1][c + 1][2] += dist[r][c][d]

print(sum(dist[-1][-1]))

✅ 풀이 한줄 설명:
총 이동 거리가 적은 순서대로 queue 에 요소를 넣고 빼며 다음 칸에 대해 확인하는 BFS 풀이이다.

✅ 풀이 자세한 설명:
코드만 대충 보면 일반적인 BFS와 매우 다르게 생겼지만 실질적으로 BFS 풀이이다.
우선 일반적인 BFS와 다른 문제의 특이사항을 살펴보면 다음과 같다.

🍎 문제의 특이점으로 인한 상황 파악하기

파이프를 한번 움직일 때, 거리상 1칸 이동하는 경우와 2칸 이동하는 경우가 섞여있다.
문제 목표: 목적지에 도달할 수 있는 모든 경우의 수
-> 모든 경로마다 반복적으로 수행하면 시간초과 (1번 풀이 참고)
-> 중복을 줄이기 위해, 같은 상태(좌표, 방향이 같은 경우) 반복하지 않아야 한다.
-> 따라서 총 이동 거리가 적은 순으로 queue에 요소를 넣고 빼며 BFS를 돌려야 한다.
-> heapq 필요
행, 열 제외한 관리할 상태값(방향)이 더 있다.
-> dist를 3차원으로 관리해야 한다.

🍎 특이점 고려하여 코드 작성하기
우선 위의 2번 특이점을 고려하여 dist를 다음과 같이 둔다.

# 가장 안쪽 리스트의 인덱스는 방향 [가로:0,세로:1,대각선:2]
dist = [[[0] * 3 for _ in range(n)] for _ in range(n)]
dist[0][1][0] = 1 # (0, 1) 가로

그리고 위의 1번 특이점을 고려하여 heapq를 활용해 다음과 같이 초기 설정을 한다.

pq = [] # priority_queue
heapq.heappush(pq, (1, (0, 1, 0))) # 우선순위: r + c

pq에서 요소를 하나씩 빼면서, 현재 상황에 따라 가로, 세로, 대각선으로 갈 수 있는지 확인한다. 가로로 갈 수 있는 경우만 살펴보자.

# 가로로 갈 수 있는 경우
# 현재 파이프가 놓인 방향이 가로 or 대각선이면서
# 현재 (행 + 1)이 범위를 벗어나지 않으면서
# matrix[r][c + 1]이 벽이 아니면
# 가로로 한 칸 이동 가능하다
if d in (0, 2) and c + 1 < n and matrix[r][c + 1] == 0:
	# 다음 칸에 가로로 처음 도달하는 것이면 pq에 요소 추가
	if dist[r][c + 1][0] == 0:
		heapq.heappush(pq, (p + 1, (r, c + 1, 0)))
    # dist 값 업데이트
	dist[r][c + 1][0] += dist[r][c][d]

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '17070. 파이프 옮기기 1'
GitHub - [9강] BFS/응용문제 '17070. 파이프 옮기기 1'

✅ 비고

💫 목적지에 도달하는 모든 경우의 수를 구하는 문제면 DP가 더 효율적일 수도!
→ BFS는 예외처리 해줄 것이나 더 고려할 것이 많아진다. 잘 처리하지 않으면 시간초과가 날 확률이 높다.

BFS 응용 문제

⚠️ 칸을 한번 움직일 때, 1칸 이동하는 경우와 n칸 이동하는 경우가 섞여있음

문제 목표: 목적지에 도달할 수 있는 경우의 수
- 모든 경로마다 반복을 수행하면 시간초과
- 중복을 줄이기 위해, 같은 상태(좌표와 방향)이 같은 경우 반복하지 않음
- 따라서 적게 이동한 순으로의 BFS 필요 (적게 이동한 순으로 queue 에 요소를 넣고 빼며 BFS 돌려야 함 - 총 이동 거리가 짧은 순대로!)
  - 이동 거리가 일정하게 늘어나지 않음
  - FIFO를 할 수 없는 상황이 됨
    - heapq 필요
문제 목표: 이동 횟수, 최소 시간, 최소 비용 기준으로의 BFS (말이 되고 싶은 원숭이 문제)
- ~~이동 거리가 일정하게 늘어날 필요가 없음~~
- BFS에 해당 칸에 도달하는 순서대로 요소를 deq 에 넣고 빼면 됨 (해당 칸 재방문 시에는 deq 에 넣을 필요X)
- FIFO 해야 됨
  - deque 써도 됨