백준 2146번: 다리 만들기
일반적인 BFS를 생각해보자. 한 출발점을 기준으로 상하좌우 최단경로를 탐색하면 된다.
기본만 짚고 넘어가자면, BFS는 그래프의 모든 간선의 가중치가 동일할 때에만 최단 경로를 구할 수 있다.
2차원 배열이 나오면 BFS를 주로 쓰는 이유도 그 때문이다.
2차원 배열은 각 칸 (i, j)이 정점이고 간선의 가중치가 1로 동일한 그래프로 생각할 수 있다.
BFS 1: 한 출발점과 도착점이 정해져 있는 경우
따라서 2차원 배열에 어떤 한 출발점과 어떤 한 도착점이 정해져 있다면 BFS를 써서 아주 답을 쉽게 구할 수 있다.
2206번(벽 부수고 이동하기)이 그 예다. 물론 이건 다른 조건이 붙어서 어려워지지만...
2146번도 저 아이디어를 활용하면 풀 수 있다.
우선 모든 섬에 대해 각 섬을 구분할 수 있도록 2차원 배열에 번호(idx_island)를 매긴 후,
각 섬에 속하는 칸에 대해서 BFS를 수행한다.
만약 중간에 현재 섬이 아닌 다른 섬(idx_island 변수로 구분)을 만난다면 탐색을 중단하고 현재까지 구한 거리를 기록한다.
이 과정을 모든 섬에 대해 반복해서 최단 거리로 업데이트한다.
저 아이디어를 구현한 코드는 다음과 같다.
첫번째: 단순하지만 무식한 풀이
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[False]*N for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs_for_land(start_x, start_y, idx_island):
q = deque([(start_x, start_y)])
visited[start_x][start_y] = True
board[start_x][start_y] = idx_island
while q:
x, y = q.popleft()
for i in range(4):
mx, my = x+dx[i], y+dy[i]
if 0 <= mx < N and 0 <= my < N and board[mx][my] == 1 and not visited[mx][my]:
visited[mx][my] = True
board[mx][my] = idx_island
q.append((mx, my))
def bfs_for_path(cur_island):
dist = [[-1]*N for _ in range(N)]
q = deque()
for r in range(N):
for c in range(N):
if board[r][c] == cur_island:
q.append((r, c))
dist[r][c] = 0
while q:
x, y = q.popleft()
for i in range(4):
mx, my = x+dx[i], y+dy[i]
if not (0 <= mx < N and 0 <= my < N):
continue
if board[mx][my] > 0 and board[mx][my] != cur_island:
return dist[x][y]
if board[mx][my] == 0 and dist[mx][my] == -1:
dist[mx][my] = dist[x][y] + 1
q.append((mx, my))
# 1. 각 섬을 구분한다.
idx_island = 1
for r in range(N):
for c in range(N):
if not visited[r][c] and board[r][c] == 1:
bfs_for_land(r, c, idx_island)
idx_island += 1
# 각 섬 사이 최단 경로를 구한다.
answer = float('inf')
for cur_island in range(1, idx_island):
cur_min = bfs_for_path(cur_island)
answer = min(answer, cur_min)
print(answer)
그런데 사실 각 섬에 대해 거리를 탐색하고 업데이트하는 과정은 비효율적이다.
내가 1번째 섬에 대해 BFS를 수행해서 2번째 섬에 가장 먼저 닿았다면,
나중에 2번째 섬에 대해 탐색할 때 1번째 섬은 탐색에서 제외해도 되지만 저 코드로는 불가능하다.
게다가 문제에서 요구하는 건 모든 섬 사이 최단 거리다.
최단 거리를 구하기까지 각 두 섬 사이 거리를 일일이 모두 구해야 하기 때문에 이 또한 비효율적이다.
지금은 문제의 입력 N의 크기가 그리 크지 않기 때문에(100 이하) 시간 초과가 나지 않고 통과하지만
만약 섬의 개수가 늘어나고 N의 크기도 커진다면 불필요한 연산 때문에 시간 초과가 날 우려가 있다.
BFS 2: 출발점이 여러 곳 있는 경우(동시 탐색)
만약 각 섬의 한칸 한칸에 대해 BFS를 수행하는 게 아니라
모든 섬에 대해 동시에 BFS를 수행한다면, 최단 거리를 같은 타이밍에 구할 수 있지 않을까?
각 섬에 대해 한 칸씩 확장해간다고 생각하자.
그럼 한 걸음씩 확장하면서 결국 확장된 영역이 겹치는 그 순간이 최단 거리가 된다.
물론 한 iteration에서 모든 섬에 대해 BFS를 수행해야 하기 때문에 위 코드보다 한 iteration 수행 시간이 길어지겠지만
최단 거리를 구하기까지 과정이 더 단축된다.
이 BFS 방법을 '동시 탐색'이라고 하겠다.
그럼 말 그대로 '각 섬에 대해 한 걸음씩 BFS를 수행'하는 코드를 살펴보자.
참고로 이 코드는 썩 좋지 않은 코드니까 이해하려 하지 말고 대충 보고 넘어가면 된다.
BFS 동시 탐색 풀이(추천 X)
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[False]*N for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs_for_land(start_x, start_y, idx_island):
q = deque([(start_x, start_y)])
visited[start_x][start_y] = True
board[start_x][start_y] = idx_island
while q:
x, y = q.popleft()
for i in range(4):
mx, my = x+dx[i], y+dy[i]
if 0 <= mx < N and 0 <= my < N and board[mx][my] == 1 and not visited[mx][my]:
visited[mx][my] = True
board[mx][my] = idx_island
q.append((mx, my))
def bfs_all_island(num_island):
distances = [[-1]*N for _ in range(N)]
queues = [deque() for _ in range(num_island)]
visited = [[-1]*N for _ in range(N)]
stop_search = False
answer = -1
for r in range(N):
for c in range(N):
for cur_island in range(1, num_island+1):
if board[r][c] == cur_island:
queues[cur_island-1].append((0, r, c))
distances[r][c] = 0
visited[r][c] = cur_island
# N*N 보드에서 섬 간 가능한 최대 거리는 2N-2, 근데 그냥 편의상 2*N이라 하자.
for step in range(2*N):
if stop_search:
break
for cur_island in range(1, num_island+1):
while queues[cur_island-1]:
cur_d, x, y = queues[cur_island-1].popleft()
if cur_d > step:
# FIXME - 이걸 추가 안했어서 틀렸다.
queues[cur_island-1].appendleft((cur_d, x, y))
break
for i in range(4):
mx, my = x+dx[i], y+dy[i]
if not (0 <= mx < N and 0 <= my < N):
continue
if visited[mx][my] != -1 and visited[mx][my] != cur_island:
# FIXME - 바로 리턴하면 안되고, 여러 값이 나올 수 있고 최소값이 나중에 나올 수도 있기 때문에
# 업데이트를 해야 한다.
# return cur_d + distances[mx][my]
if answer == -1 or answer > cur_d + distances[mx][my]:
answer = cur_d + distances[mx][my]
stop_search = True
break
if board[mx][my] == 0 and distances[mx][my] == -1:
distances[mx][my] = cur_d + 1
queues[cur_island-1].append((cur_d+1, mx, my))
visited[mx][my] = cur_island
return answer
idx_island = 1
for r in range(N):
for c in range(N):
if not visited[r][c] and board[r][c] == 1:
bfs_for_land(r, c, idx_island)
idx_island += 1
num_island = idx_island - 1
print(bfs_all_island(num_island))
정 말 그대로 각 섬에 대해서 한 스텝씩 BFS를 수행한 코드다. 코드를 요약하자면
1) 각 섬에 대해 큐를 만들고 (큐의 리스트)
2) 각 섬에 해당하는 큐마다 섬의 칸을 대입해서 수행
3) 현재 이동한 횟수를 1,2,3... 씩 증가시키면서 2)를 수행
돌악가긴 하지만 결과적으로 코드가 많이 복잡해진다.
하지만 결국 모든 섬은 2차원 배열 안에 포함되어 있으므로 이렇게 바꿀 수 있다.
1) 2차원 배열에 각 섬을 인덱스(idx_island)로 표시 -> island 라는 배열을 별도 생성
2) 2차원 배열의 각 칸에 대해 반복문을 돌면서 만약 이동한 칸이 섬(아무 섬이든 상관없다)이라면 BFS 수행
3) island라는 배열에 어떤 섬에서 BFS를 시작했는지 기록 및 저장
4) 만약 이동한 칸의 island 배열 값이 이미 존재하고, 현재 섬과 다른 섬이라면 최단거리를 업데이트
아래 코드에서 핵심은 3번이다.
즉 Dynamic Programming(동적계획법)처럼 어느 섬(출발점)에서 BFS 탐색을 출발했는지 계속 기록해나가는 것이다.
2번 아이디어는 굳이 말하자면 완전탐색의 백트래킹이라고 할 수 있겠지만 워낙 보편적인 접근방식이기도 하다.
말로 설명하면 역시 이해가 안되니까 코드를 읽어보자.
BFS 동시 탐색 풀이 (추천 O)
from collections import deque
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
way = [[0]*N for _ in range(N)]
island = [[0]*N for _ in range(N)]
Q = deque()
for i in range(N):
# row = list(map(int, input().split()))
for j in range(N):
# board[i][j] = row[j]
if board[i][j] == 1:
Q.append((i, j))
way[i][j] = 0
elif board[i][j] == 0:
way[i][j] = -1
num_island = 0
for i in range(N):
for j in range(N):
if not board[i][j] or island[i][j] > 0:
continue
num_island += 1
QI = deque()
island[i][j] = num_island
QI.append((i, j))
while QI:
x, y = QI.popleft()
for d in range(4):
mx, my = (x + dx[d], y + dy[d])
if mx < 0 or my < 0 or mx >= N or my >= N:
continue
if not board[mx][my] or island[mx][my] > 0:
continue
island[mx][my] = num_island
QI.append((mx, my))
bridge = N + N
while Q:
x, y = Q.popleft()
for d in range(4):
mx, my = (x + dx[d], y + dy[d])
if mx < 0 or my < 0 or mx >= N or my >= N:
continue
if island[mx][my] == island[x][y]:
continue
if island[mx][my] != 0:
bridge = min(bridge, way[x][y] + way[mx][my])
continue
island[mx][my] = island[x][y]
way[mx][my] = way[x][y] + 1
Q.append((mx, my))
print(bridge)
중간에 디버깅하느라 여러 번 틀렸지만 시간 복잡도만 보면 꽤 줄어든 걸 확인할 수 있다.
첫번째 풀이가 348ms, 두번째 풀이가 284ms, 세번째 풀이가 192ms이다.
세번째 풀이에서도 island 배열을 board 배열과 합치거나 하는 방식으로 좀 더 시간을 줄일 수 있겠지만
그렇게 되면 바다(0으로 표시)와 섬의 인덱스(0부터 시작)를 별도로 구분해주어야 하기 때문에 헷갈릴 수도 있어
내버려두었다.
BFS: 동시 탐색 유형 정리
- 출발점이 여러 개 있고 각 출발점 사이 최단거리를 구하고자 할 때 쓰인다.
- 다이나믹 프로그래밍처럼 어느 출발점에서 BFS 탐색을 시작했는지 별도의 배열에 기록해나가면서 탐색한다.
- 각 출발점에 대해 큐를 별도로 생성 후 BFS 탐색하는 게 아니라, 모든 지점에 대해 전체적으로 BFS를 수행한다.
