누가 내 집에 바로 가는 다리 하나 놓아줘..
BOJ 2146 - 다리 만들기 링크
(2022.09.21 기준 G3)
(치팅하면 퇴근 못함)
문제
육지가 1, 바다가 0인 지도가 주어진다면, 섬끼리 잇는 다리 중 가장 짧은 길이
알고리즘
섬끼리 잇는 가장 짧은 길이를 구하려면 먼저 육지로부터 BFS을 해나가야 한다.
그리고 같은 섬끼리 이으면 안되므로, 이어진 육지끼리 연결해야 하므로 이 때 BFS를 이용한 플러드 필을 이용하자.
풀이
우선 이어진 육지끼리 하나의 섬으로 만들어야 한다. 여기서 플러드 필을 사용해야 하는데, 말만 거창하고 간단한 방법이다.
먼저 섬 넘버링을 한다고 생각하면 0이 바다, 1이 육지이므로 2부터 넘버링을 하자.
지도 전체를 탐색을 하면서 1인 곳을 찾자. 1인 곳은 넘버링이 되지 않은 육지이다.
그러면 이 육지로부터 이어진 육지를 BFS로 찾아나가면서 같은 숫자로 넘버링을 해주면 된다.이 과정이 플러드 필이다. 하나의 섬을 전부 찾으면 넘버링할 숫자를 1 증가시키고 다시 1인 육지를 찾아나가면서 지도 전체를 탐색하면 된다.
그런데 이 문제에선 한 섬으로부터 다른 섬으로까지의 다리. 즉, 거리를 찾아야 한다. 그러므로, 플러드 필 과정에서 BFS를 할 때, 다음 위치가 바다라면 섬 테두리일 가능성이 높으므로 queue에 따로 저장해두자. 이 때, visited 배열을 3차원으로 선언하여 위치마다 다리 길이와 시작한 섬을 저장하자.
나중에 섬끼리 다리를 이을 때, 다른 섬으로부터 나온 다리를 만나게 되면 두 다리를 합치면 두 섬을 잇는 다리가 된다. 또한, 같은 섬에서 나온 다리를 만나면 그 위치로의 탐색을 중지해야 한다. 이를 visited 배열에 다리 길이와 시작한 섬을 저장하면 관리하기 쉬워진다.
섬 테두리를 저장하는 과정에서 만약, 다른 섬으로부터 나온 다리를 만나면. 즉, 다른 섬의 테두리이면 다리 길이가 1이 된다. 바로 이어지기 때문. 그러므로 이 경우엔 1을 출력하고 프로그램 자체를 중지하면 된다.위와 같은 과정이 끝나면 이제 섬 테두리로부터 시작하는 다리를 늘려가면서 다른 섬으로부터 나오는 다리를 만나가야 한다.
여기선 평범한 BFS가 된다. 방문한 적이 없으면 나아가고, 같은 섬의 다리를 만나면 그 위치로의 탐색은 중지, 다른 섬의 다리를 만나면 두 다리의 길이를 합치자. 그런데 여기서 중요한 점이 있다.
두 다리가 만나면 BFS로 하였기 때문에 당연히 먼저 만났으니 가장 짧은 다리가 되겠지? 하면서 바로 출력해버릴 수 있는데 그러면 안된다.
이 반례를 살펴 보자.5
1 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 0 0 1ans 2
이 반례에서, 만약에 바로 출력해버린다면, 위에서부터 큐에 담겨서 BFS가 진행되므로 다리의 길이가 3으로 출력이 될 것이다.
그러므로 그냥 다리가 만날 때마다 두 다리의 길이를 합쳐 저장해두고 BFS가 전부 끝나면 마지막에 최솟값을 출력하자.생각보다 구현이 좀 있는 BFS라서 글로만 설명하기 까다롭다.
코드에 자세한 주석을 달았으니 참고하면서 보자.
코드
import sys; input = sys.stdin.readline
from collections import deque
N = int(input()) # 지도의 크기
matrix = [list(map(int, input().split())) for _ in range(N)] # 지도
island = 2 # 0 - 바다, 1 - 육지이므로 2번부터 넘버링
queue = deque() # 섬 끝에서 다른 섬으로 탐색 시작하는 위치들 저장
visited = [[[0, 0] for _ in range(N)] for __ in range(N)] # (다리 길이, 섬 번호)로 이루어진 visited 배열
for n in range(N):
for m in range(N):
if matrix[n][m] == 1: # 방문하지 않은 섬이면
# 플러드 필 시작
matrix[n][m] = island # 시작 섬은 먼저 넘버링해주고 덱에 담자.
fill = deque([(n, m)])
# 방문체크는 섬 넘버링이 있기 때문에 따로 visited 배열을 쓰지 않아도 된다.
while fill:
i, j = fill.popleft()
for ii, jj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: # 상하좌우
if 0 <= ii < N and 0 <= jj < N: # 지도의 범위 안이어야 한다.
if matrix[ii][jj] == 1: # 다음 위치가 육지면 붙어있으므로 같은 섬이다.
matrix[ii][jj] = island
fill.append((ii, jj))
elif not matrix[ii][jj]: # 다음 위치가 바다라면 현재 위치에서 다른 섬으로 탐색 시작하는 위치가 될 수 있다.
if not visited[ii][jj][1]: # 그리고 방문한 적도 없어야 탐색 가능하다.
queue.append((ii, jj, 1, island)) # 다음위치 ii, jj, 다리 길이, 시작한 섬 번호
visited[ii][jj] = [1, island]
elif visited[ii][jj][1] == island: # 혹시 같은 섬으로부터 나온 다리가 이미 있다면
continue # 패스
else: # 위 두 if문에 해당하지 않으면 다른 섬으로부터 나온 다리랑 만났다는 것이다.
print(1) # 그러면 다리 길이는 1이 된다. 출력 후 프로그램 중지
exit()
# 한 섬의 플러드 필이 끝났다면 섬 번호는 1 증가시키자.
island += 1
# 지도 탐색이 끝났다면 이제 다리를 놓아보자.
# queue에 담았던 (위치, 다리 길이, 섬 번호)로 BFS를 하여
# 다른 섬으로부터 시작한 다리를 만나면, 두 다리의 길이를 합쳐 result에 넣자.
# 탐색이 끝나면 result의 최솟값 출력
result = []
while queue:
i, j, length, start = queue.popleft()
for ii, jj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: # 상하좌우
if 0 <= ii < N and 0 <= jj < N: # 지도의 범위 안이어야 한다.
if not visited[ii][jj][1]: # 방문한 적이 없는 위치이고
if not matrix[ii][jj]: # 그 위치가 바다이면
visited[ii][jj] = [length + 1, start] # 그 방향으로 다리가 나아감
queue.append((ii, jj, length + 1, start))
# 그 위치가 바다가 아니고 시작 섬이 아닐 경우는 절대 없다.
# 이미 섬 테두리에 visited 체크를 해놓았고
# 길이가 1로 바로 만나는 경우는 전 단계에서 체크했기 때문이다.
# 그러므로 바다가 아니면 시작 섬으로 되돌아가는 경우이므로 패스
elif visited[ii][jj][1] != start: # 만약 다른 섬으로부터 나온 다리가 있으면
# 두 다리를 합치면 두 섬을 잇는 다리가 된다.
result.append(visited[ii][jj][0] + length)
# 위 두 if문에 해당하지 않으면 같은 섬에서 나온 다리를 만난 것이므로
# 다음 위치에서 먼저 나아간 다리가 있다는 것이므로 이 다음 위치는 패스
print(min(result))여담
사실 다리 만들기 2 문제 풀이를 적을까 하다가, 다리 만들기 1은 무슨 문제지 싶어서 풀었다가 생각보다 까다로운 문제여서 당황했다.
2는 첫 시도에 AC, 1은 시도 6번만에 AC..
