백준 1174 - 우주신과의 교감

1774번: 우주신과의 교감 (acmicpc.net)

1774번: 우주신과의 교감

 

문제를 살펴보면서 "새로 만들어야 할 정신적인 통로의 길이들이 합이 최소가 되게 통로를 만들어 “빵상”을 외칠수 있게 도와주자." 이 문장과 좌표들을 입력받는 것을 통해 거리의 합을 구하고, 최소가 될 수 있는 통로를 만들어주어야 한다고 생각했다.

문제를 보면 예전에 풀어보았던 최소 스패닝 트리 문제가 떠오르게 되어, 전체적인 알고리즘을 최소 스패닝 트리 문제와 동일하게 가져갔다.

 

※ 최소 스패닝 트리란?

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 크루스칼 알고리즘을 생각하면서, 아래와 같은 코드로 최소 스패닝 트리를 만들 수 있다.

그렇다면 크루스칼 알고리즘은 또 무엇일까?

 

크루스칼 알고리즘 : 모든 간선을 길이에 따라 오름차순으로 정렬하여 크기가 작은 간선부터 사용하는 알고리즘으로, 간선을 사용했을 때 사이클이 발생하지 않는지를 체크한다.

import sys

input = sys.stdin.readline

v, e = map(int, input().split())
parent = [i for i in range(v+1)]

def find(parent, x):
    if parent[x] != x:
        parent[x] = find(parent, parent[x])
    return parent[x]

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

edge = []
cost = 0

for i in range(e):
    a, b, c = map(int, input().split())
    edge.append((c, a, b))

edge.sort()

for i in range(e):
    c, a, b = edge[i]
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
        cost += c

print(cost)

 

크루스칼 알고리즘을 이용한 최소 스패닝 트리는 union - find를 사용하면 쉽게 처리할 수 있기 때문에, 최소 스패닝 트리의 알고리즘을 그대로 가져가면서 위 문제에 맞게 적용시키면 된다.

 

1. union - find 알고리즘을 그대로 구현해서, x가 속한 집합의 루트 노드 값을 찾아준다.

2. union-find 연산을 통해 서로소 집합의 자료구조 DisjointSet을 구성해 준 후에 각 노드 좌표 간의 거리를 직접 수식으로 계산하여 cost 값으로 나타내어준다.

3. 나타난 cost 값과 위치를 edges 리스트에 담아 나타내어준다.

4. edges 리스트를 정렬시킨 상태에서 cost와 각 노드 위치들을 for문을 통해 최소 비용의 합계를 구해준다.

import sys
import math
input = sys.stdin.readline

class DisjointSet:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX < rootY:
            self.parent[rootY] = rootX
        else:
            self.parent[rootX] = rootY

n, m = map(int, input().split())
nodes = [tuple(map(int, input().split())) for _ in range(n)]
disjoint_set = DisjointSet(n)
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    disjoint_set.union(a, b)

for i in range(n):
    for j in range(i + 1, n):
        cost = math.sqrt((nodes[i][0] - nodes[j][0]) ** 2 + (nodes[i][1] - nodes[j][1]) ** 2)
        edges.append((cost, i + 1, j + 1))

total_cost = 0
for cost, node1, node2 in sorted(edges):
    if disjoint_set.find(node1) != disjoint_set.find(node2):
        disjoint_set.union(node1, node2)
        total_cost += cost

print(f"{total_cost:.2f}")

 

이렇게 구현할 수 있다. 전체적으로 긴 줄글로 표현이 되어 있는 문제이지만, 마지막 통로의 길이들의 합이 최소가 되게 통로를 만들고 싶다는 문장 하나를 통해서 알고리즘을 예측할 수 있고, 기존에 풀어보았던 최소 스패닝 트리를 이용하면 된다는 생각을 하게 되면 매우 간단하게 문제를 해결할 수 있을 것이다.