[백준 1774] 우주신과의 교감 (Python)

문제

황선자씨는 우주신과 교감을 할수 있는 채널러 이다. 하지만 우주신은 하나만 있는 것이 아니기때문에 황선자 씨는 매번 여럿의 우주신과 교감하느라 힘이 든다. 이러던 와중에 새로운 우주신들이 황선자씨를 이용하게 되었다.

하지만 위대한 우주신들은 바로 황선자씨와 연결될 필요가 없다. 이미 황선자씨와 혹은 이미 우주신끼리 교감할 수 있는 우주신들이 있기 때문에 새로운 우주신들은 그 우주신들을 거쳐서 황선자 씨와 교감을 할 수 있다.

우주신들과의 교감은 우주신들과 황선자씨 혹은 우주신들 끼리 이어진 정신적인 통로를 통해 이루어 진다. 하지만 우주신들과 교감하는 것은 힘든 일이기 때문에 황선자씨는 이런 통로들이 긴 것을 좋아하지 않는다. 왜냐하면 통로들이 길 수록 더 힘이 들기 때문이다.

또한 우리들은 3차원 좌표계로 나타낼 수 있는 세상에 살고 있지만 우주신들과 황선자씨는 2차원 좌표계로 나타낼 수 있는 세상에 살고 있다. 통로들의 길이는 2차원 좌표계상의 거리와 같다.

이미 황선자씨와 연결된, 혹은 우주신들과 연결된 통로들이 존재한다. 우리는 황선자 씨를 도와 아직 연결이 되지 않은 우주신들을 연결해 드려야 한다. 새로 만들어야 할 정신적인 통로의 길이들이 합이 최소가 되게 통로를 만들어 “빵상”을 외칠수 있게 도와주자.

문제 해결 전략

풀이 방식의 선택

이 문제는 2차원 좌표계 상에 몇개의 좌표가 주어질 때 이들간에 몇 개를 직선으로 연결해 가장 짧은 길이로 모든 좌표를 잇는 경로의 길이를 구하는 문제이다.

문제 해결을 위해 각각의 좌표를 정점으로, 좌표간 통로를 간선으로 사용하는 그래프에 대해 모든 정점을 잇는 가장 짧은 스패닝 트리, 즉 최소 스패닝 트리를 구하는 문제로 해석할 수 있다. 이 때 탐색의 기준으로 삼을 간선의 가중치는 곧 2차원 좌표계 상 좌표간 거리로 나타낼 수 있을 것이다.

최소 스패닝 트리 알고리즘의 선택

최소 스패닝 트리 문제를 해결하는 알고리즘은 크게 크루스칼, 프림 알고리즘이 있다.

해당 문제는 2차원 평면상 모든 노드간 연결을 검토하여 가장 짧은 거리로 모든 노드를 연결할 수 있는 경로를 구성하는 문제이다. 문제에 주어진 모든 노드간 연결을 확인하여야 하므로 밀집 그래프에 해당해 밀집 그래프에서 더 효율적인 프림 알고리즘으로 문제를 해결하고자 하였다.

문제 특이사항의 고려

문제는 모든 노드에 대해 처음부터 최소 스패닝 트리를 구축하는 것이 아니라 이미 몇 개의 연결 관계가 구축되어있고 연결되지 않은 노드에 확장하는 경로 중 최소 비용을 찾아야 한다.

문제는 해결하기 위해 프림 알고리즘을 그대로 적용하도록 하였다. 전체 n개 노드 개수만큼 반복하여 트리를 확장하는 최소 경로를 탐색하여 트리를 완성하도록 하였다.

다만 보통의 프림 알고리즘 문제 풀이와 다른 것은 특정 간선을 반드시 선택하게끔 유도하는 것이다. 모든 노드에 대해 순회하되 미리 구축된 간선을 발견했을때 이를 강제로 선택하게끔 하는 것이다.

이를 가능하게 하기 위해 그래프 인접 행렬의 모든 정점간 거리를 계산하는 과정에 입력으로 주어진 m개 간선에 대해서는 그 거리를 0으로 초기화해주었다. 좌표간 거리는 0보다 작을 수 없기 때문이다. 정점별 인접한 간선을 조사하는 중 거리가 0인 간선을 발견한다면 이를 우선적으로 이용해 스패닝 트리를 구축할 것이다.

정답 코드

import sys

def prim(n):
    INF = 10 ** 8
    added = [False for _ in range(n)]  # type: list[bool]. 좌표별 트리 추가 여부
    current_min_distance = [INF for _ in range(n)]  # type: list[int]. 좌표별 현재 트리까지의 최단거리
	# 주의! 이미 추가된 좌표 및 간선에 대해 별도 처리하지 않는다.

    result = 0

	# 0번 좌표부터 시작. 첫 좌표의 트리까지 최단거리 0으로 저장
    current_min_distance[0] = 0

	# 전체 좌표 개수만큼 반복한다.
    for _ in range(n):
		# 현재 트리에 추가되지 않는 좌표중 트리와 가장 가까운 좌표와 그 거리를 구한다.
        min_v = None
        min_distance = INF
        for i in range(n):
            if not added[i] and min_distance > current_min_distance[i]:
                min_v = i
                min_distance = current_min_distance[i]

		# 선택된 노드를 트리에 추가한다.
        added[min_v] = True
        result += min_distance

		# 선택된 노드에 인접한 간선들에 대해 최단거리를 업데이트한다.
        for i in range(n):
            if not added[i] and current_min_distance[i] > graph[min_v][i]:
                current_min_distance[i] = graph[min_v][i]

    return result

n, m = [int(i) for i in sys.stdin.readline().rstrip().rsplit()]

vertices = [[int(i) for i in sys.stdin.readline().rstrip().rsplit()] for _ in range(n)]
edges = [[int(i) - 1 for i in sys.stdin.readline().rstrip().rsplit()] for _ in range(m)]

# n*n 인접 행렬에 좌표간 거리 저장
graph = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(i + 1, n):
        x1, y1 = vertices[i]
        x2, y2 = vertices[j]
        graph[i][j] = graph[j][i] = ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

# 인접 행렬 내 이미 연결된 통로에 대해서 거리 0으로 저장
for i, j in edges:
    graph[i][j] = graph[j][i] = 0

print('{:.2f}'.format(round(prim(n), 2)))