-
백준 1174 - 우주신과의 교감Algorithm/Graph 2024. 1. 14. 11:29728x90
문제를 살펴보면서 "새로 만들어야 할 정신적인 통로의 길이들이 합이 최소가 되게 통로를 만들어 “빵상”을 외칠수 있게 도와주자." 이 문장과 좌표들을 입력받는 것을 통해 거리의 합을 구하고, 최소가 될 수 있는 통로를 만들어주어야 한다고 생각했다.
문제를 보면 예전에 풀어보았던 최소 스패닝 트리 문제가 떠오르게 되어, 전체적인 알고리즘을 최소 스패닝 트리 문제와 동일하게 가져갔다.
※ 최소 스패닝 트리란?
최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 크루스칼 알고리즘을 생각하면서, 아래와 같은 코드로 최소 스패닝 트리를 만들 수 있다.
그렇다면 크루스칼 알고리즘은 또 무엇일까?
크루스칼 알고리즘 : 모든 간선을 길이에 따라 오름차순으로 정렬하여 크기가 작은 간선부터 사용하는 알고리즘으로, 간선을 사용했을 때 사이클이 발생하지 않는지를 체크한다.
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}")
이렇게 구현할 수 있다. 전체적으로 긴 줄글로 표현이 되어 있는 문제이지만, 마지막 통로의 길이들의 합이 최소가 되게 통로를 만들고 싶다는 문장 하나를 통해서 알고리즘을 예측할 수 있고, 기존에 풀어보았던 최소 스패닝 트리를 이용하면 된다는 생각을 하게 되면 매우 간단하게 문제를 해결할 수 있을 것이다.
728x90'Algorithm > Graph' 카테고리의 다른 글
백준 14502 - 연구소 (0) 2024.04.04 백준 1949 - 우수 마을 (0) 2024.03.05 백준 1956 - 운동 (1) 2024.01.07