[백준] 2887번 : 행성터널

2887번: 행성 터널

2887번: 행성 터널

🤔 문제분석

크루스칼 알고리즘을 알고 있어야 해당 문제를 해결 할 수 있다.

N-1개의 터널을 모두 건설하여( 최소산장트리의 간선의 개수) 행성들이 모두 연결된 상태를 만들어야한다.

또한, 간선의 개수를 구할때 O(n^2)이 아닌 O(3N)으로 해결 할 수 있는데, 비용을 계산할때, x와 y와 z를 각각 독립적으로 계산하여 간선에 누적한다.

📝 의사코드

1. 간선을 만든다.
   1. x, y, z를 각각 분리하여 만들고, ( 거리, 노드1, 노드2 ) 형태로 받는다.
2. 간선을 거리의 순으로 정렬한다.
3. 크루스칼 알고리즘을 통하여 최소신장트리를 구하고, 모든 합을 누적한다.

💻 코드

import sys

input = sys.stdin.readline

N = int(input())
parent = [i for i in range(N)]
planet = [[] for _ in range(3)]
for i in range(N):
    a, b, c = map(int, input().split())
    planet[0].append((a, i))
    planet[1].append((b, i))
    planet[2].append((c, i))

def find(a):
    if parent[a] != a:        
        return find(parent[a])
    else:
        return a

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

def get_distance(n1, n2):
    return abs(n1 - n2)

distance = []

planet[0].sort(key=lambda x:x[0])
planet[1].sort(key=lambda x:x[0])
planet[2].sort(key=lambda x:x[0])

for node in range(N-1):
    for i in range(3):
        distance.append((get_distance(planet[i][node-1][0], planet[i][node][0]), planet[i][node-1][1], planet[i][node][1]))
        distance.append((get_distance(planet[i][node][0], planet[i][node+1][0]), planet[i][node][1], planet[i][node+1][1]))
        
distance.sort()
ans = 0
for dis, node, new_node in distance:
    v1 = find(node)
    v2 = find(new_node)
    if v1 != v2:
        ans += dis
        union(node, new_node)

print(ans)

🎯 피드백 및 개선사항

처음에 크루스칼 알고리즘을 활용하여 풀어야 한다는것을 알았고, x, y, z를 각각 독립적으로 계산을 해야한다는 것을 늦게 파악하여 문제를 늦게 해결하였습니다. 😢