백준 17472번 : 다리 만들기 2 in Python
이 문제는 섬으로 이루어진 나라를 다리로 연결할 때 다리의 길이의 합의 최솟값을 구하는 문제이다. 단, 다리의 방향이 중간에 바뀌면 안되고, 다리의 길이가 2 이상이어야 한다. 또한 다리가 중간에 다른 섬과 인접한다고 해서 그 섬과 인접하다고 이야기하지 않는다. 또한 다리를 만들 때 반드시 가로 방향이나 세로 방향으로 일직선을 이뤄야 하고 다리의 양 끝은 다리 방향과 같은 방향으로 섬과 인접해야 한다.
이 문제는 결국 분리된 섬들을 최소 길이의 간선들을 이용해 모두 연결시켜야 하므로 최소 스패닝 트리를 만드는 문제라 할 수 있다. 다만, 분리된 섬들이 여러 좌표들의 모임으로 표현되고, 다리는 가로 방향 혹은 세로 방향으로만 설치 가능하며, 다리의 최소 길이가 2 이상이어야 한다.
이를 주의하며 코드를 하나씩 작성해보자. 우선 궁극적으로 Kruskal's Algorithm을 사용하려면 그래프 내의 각 정점들과 간선들을 적절한 방식으로 표현해야 한다.
먼저 정점들의 경우 궁극적으로 각 정점 하나 당 하나의 자연수로 표현해야 한다. 이는 각 섬에 대해 섬의 좌표들을 모두 모은 배열을 만들고, 이를 하나의 자연수에 대응하는 값으로 한다. 이러한 방식으로 dictionary 자료형을 만들면 각 섬을 하나의 자연수로 표현하는 것이 가능하다. 이렇게 표현한 섬들의 모임을 dic_islands라 하자.
이 때 각 섬의 모든 좌표들을 모을려면 이전의 단지번호붙이기 문제처럼 DFS나 BFS와 같은 그래프 탐색을 이용해야 한다.
그런 다음 이제 임의의 두 섬 사이의 다리의 길이를 구해야 하는데, 이는 섬의 형태가 여러 가지임에 대비해 두 섬 각각의 모든 좌표들에 대해 순회하면서 x좌표와 y좌표 중 하나가 같고, 좌표 사이에 육지가 없으며, 다리 길이가 2 이상인 경우만 고려해 그중 길이가 가장 짧은 다리를 고른다. 이렇게 하면 두 섬 사이의 최단 거리의 다리를 찾게 되고, 이는 곧 최소 스패닝 트리의 간선 후보가 된다.
이후 Kruskal's Algorithm만 구현해 최소 스패닝 트리의 간선의 길이의 합만 구하면 문제를 해결할 수 있다. 단, 어떤 섬과도 연결될 수 없는 섬이 존재할 경우 위 구현 과정에서 sys.maxsize를 길이로 가지는 다리도 포함하게 돼 간선의 길이의 합이 sys.maxsize보다 커지게 된다. 이때는 -1을 출력한다.
이를 코드로 구현하면 다음과 같다.
import sys
import heapq
input = sys.stdin.readline
def find(u):
if parent[u] == u: return u
parent[u] = find(parent[u])
return parent[u]
def union(u, v):
root_u = find(u)
root_v = find(v)
parent[root_u] = root_v
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 섬 내의 모든 좌표를 조사하기 위한 DFS 함수
def DFS(i, j):
global N, M
if visited[i][j] != -1: return
visited[i][j] = 0
island.append([i, j])
for k in range(4):
next_i = i + dx[k]
next_j = j + dy[k]
if 0<=next_i<N and 0<=next_j<M and country[next_i][next_j] == 1:
DFS(next_i, next_j)
# 해당 다리가 문제의 조건을 만족하는 다리인지를 검사하는 함수
def bridge_valid(a, b, x_fixed, fixed_coord):
# 길이가 2 이상인지 검사한다.
if abs(b-a) <= 2: return False
# x좌표가 같은 경우
if x_fixed:
# 다리 내에 육지가 있는지 검사한다.
for i in range(min(a, b) + 1, max(a, b)):
if country[fixed_coord][i] == 1: return False
# y좌표가 같은 경우
else:
for i in range(min(a, b) + 1, max(a, b)):
if country[i][fixed_coord] == 1: return False
return True
N, M = map(int, input().split())
country = []
for i in range(N):
country.append(list(map(int, input().split())))
parent = [i for i in range(N*M+1)]
# 해당 좌표를 방문했었는지를 나타내는 행렬
visited = [[-1]*M for _ in range(N)]
# 각 섬의 좌표들을 모아 하나의 자연수에 대응시키는 dictionary 자료형
dic_islands = {}
k = 1
for i in range(N):
for j in range(M):
# 섬 위의 좌표를 발견한 경우 그 좌표에 대해 DFS를 실행해 섬 내의 모든 좌표들을 조사하고
# 이를 dic_islands에 저장한다.
if visited[i][j] == -1 and country[i][j] == 1:
island = []
DFS(i, j)
dic_islands[k] = island
k += 1
heap = []
# 임의의 두 섬 사이의 가장 짧은 다리를 조사해 heap에 넣는다.
for i in range(1, len(dic_islands)+1):
for j in range(i+1, len(dic_islands)+1):
island_a = dic_islands[i]
island_b = dic_islands[j]
min_len = sys.maxsize
for [x1, y1] in island_a:
for [x2, y2] in island_b:
if x1 == x2 and bridge_valid(y1, y2, True, x1):
min_len = min(min_len, abs(y2-y1)-1)
if y1 == y2 and bridge_valid(x1, x2, False, y1):
min_len = min(min_len, abs(x2-x1)-1)
heapq.heappush(heap, [min_len, i, j])
W = 0
while len(heap) > 0:
dis, u, v = heapq.heappop(heap)
if find(u) != find(v):
union(u, v)
W += dis
if W >= sys.maxsize:
print(-1)
else: print(W)