📌 문제
때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
📌 입력
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
📌 출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.
📌 문제 풀이
👨🏫 접근
행성을 정점, 노드로 간주하고 터널을 간선으로 생각하면, 모든 행성을 터널로 연결하는 최소 비용을 선택하므로, 모든 정점을 간선으로 연결하는 최소비용을 구하는 최소 신장 트리를 구하는 문제이다.
그렇기 때문에 크루스칼 알고리즘을 통해 모든 행성을 잇는 터널의 최소비용을 탐색하였다. 크루스칼 알고리즘은 간단하게 항상 비용이 적게 소요되는 간선을 확인하며 신장 트리를 탐색하는 것이다. 이때 A -> B, B -> C, C -> A와 같이 입력이 주어지면 A -> A로 이어지는 사이클이 발생할 수 있다. 그래서 유니온 파인드를 통해서 사이클이 발생하지 않을 때만 신장 트리를 찾도록 알고리즘을 작성한다.
그래서 대략적인 알고리즘의 흐름은 아래와 같다.
n = int(input()) # 정점의 개수
m = int(input()) # 주어지는 간선의 개수
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
parent = [i for i in range(1, n + 1)]
edges = []
for _ in range(m):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
edges.sort()
answer = 0
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
answer += cost
print(answer)이 크루스칼 알고리즘을 반영하여 문제를 풀 수 있는데, 이 문제에서는 간선이 주어지진 않고 모든 정점은 서로 이어질 수 있다. 그리고 간선의 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 그래서 모든 정점을 반복문으로 순회하면서 간선을 모두 구해서 최소 신장 트리를 위한 간선 배열을 만들어준다. 그런데, 여기서 행성은 100,000개가 주어질 수 있어서 생성될 수 있는 모든 간선의 개수는 100000 * 999999 / 2 = 4999950000 개이다. 그래서 바로 메모리 초과가 발생한다. 따라서, 다른 방법으로 간선을 저장해야 한다.
문제를 다시 읽어보면, 모든 행성은 서로 이어질 수 있다. 즉, 모든 행성이 이어질 수 있어서 행성의 번호를 고려하지 않고도 간선을 구할 수 있다는 것이다.
그러면 행성의 간선을 입력받기 위해서는 딱히 순서를 고려할 필요가 없기에 정렬을 사용할 수 있다. 정렬을 사용하면 오름차순, 내림차순으로 정렬할 수 있고, 정렬된 행성은 이웃한 행성들과 가장 가깝게 연결되어 있다는 사실을 알 수 있다. 1, 3, 8, 9, 10 이라는 배열이 있다면, 1과 가장 차이가 적은 수는 바로 이웃한 3이지 8이나 9는 절대 아니다. 그렇기 때문에 매번 정렬을 통해서 이웃한 행성과 가장 가깝게 연결될 수 있음을 알 수 있다.
이때, x, y, z의 좌표에서 가장 차이가 적은 값이 연결비용이므로 세 가지 좌표를 기준을 정렬하여 각각 간선에 값을 넣어준다. 그래서 4999950000개의 간선이 아니라 3 * 99999(간선은 정점보다 개수가 하나 더 적으므로) 개로 훨씬 더 적다.
그러면 문제를 풀이할 수 있다.
👨🏫 문제 풀이
📄 전체 코드
import sys
input = sys.stdin.readline
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
n = int(input())
graph = [[i] + list(map(int, input().split())) for i in range(n)]
cycle = [i for i in range(n)]
edges = []
for i in range(1, 4):
tmp = sorted(graph, key=lambda x: x[i])
for j in range(n - 1):
cost = abs(tmp[j][i] - tmp[j + 1][i])
edges.append((cost, tmp[j][0], tmp[j + 1][0]))
edges.sort()
ans = 0
for edge in edges:
cost, a, b = edge
if find_parent(cycle, a) != find_parent(cycle, b):
union_parent(cycle, a, b)
ans += cost
print(ans)📄 준비
import sys
input = sys.stdin.readline
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
n = int(input())
graph = [[i] + list(map(int, input().split())) for i in range(n)]
cycle = [i for i in range(n)]
edges = []두 가지 함수를 정의합니다. 부모를 찾는 연산과 부모를 찾는 연산으로 사이클을 판별한다. 그래프에서 [i] 를 더한 이유는, 정렬을 수행하면 각 행성이 무작위로 섞일 수 있기 때문이다. x, y, z를 각각 기준으로 정렬하면 매번 다른 순서로 섞이기 때문에 이를 방지하고자 임시로 인덱스를 부여했다.
사이클 발생을 판별하고자 cycle 테이블도 만들었다. 그리고 간선을 담을 edges 테이블도 만들었다.
📄 풀이
for i in range(1, 4):
tmp = sorted(graph, key=lambda x: x[i])
for j in range(n - 1):
cost = abs(tmp[j][i] - tmp[j + 1][i])
edges.append((cost, tmp[j][0], tmp[j + 1][0]))
edges.sort()
ans = 0
for edge in edges:
cost, a, b = edge
if find_parent(cycle, a) != find_parent(cycle, b):
union_parent(cycle, a, b)
ans += cost
print(ans)각각 좌표를 기준으로 정렬한 다음 이를 토대로 비용을 구하여 간선을 저장한다. 그 이후는 크루스칼 알고리즘으로 최소 신장 트리를 찾는다.
📌 총평
오랜만에 이것저것 생각하고 메모리 복잡도도 생각할 수 있는 좋은 문제였다.
