백준 2887 행성 터널 (파이썬 python)

백준 2887 행성 터널 (파이썬 python)

2887번: 행성 터널

문제 풀이 및 접근

 

N-1개의 터널, 양방향, 최소 비용(거리)을 통해 최소 신장 트리 문제임을 알 수 있고, 크루스칼 알고리즘으로 풀이 할 수 있습니다.

 

이전에 풀었던 문제는 edge의 거리(비용)이 입력 값으로 주어졌는데, 이 문제에서는 edge의 값을 구해야 했습니다. 일반적으로 for문을 두 개 중첩하여 서로 다른 임의의 두 점 사이의 거리를 구할 때 시간 복잡도는 O(N²)입니다. 하지만 입력으로 주어진 N의 범위가 100,000이고 N²이라면 백억이 됩니다. 약 1초에 1억번 연산을 하므로 이렇게 풀면 주어진 시간안에 풀이할 수 없습니다.

 

이 문제에서는 한 노드에서 다른 모든 노드와의 거리를 구하지 않고 한 노드와 가장 가까운 노드만을 찾아야합니다. 이를 찾기 위해 각 축(x,y,z)을 기준으로 정렬한 뒤 한 row와 바로 다음 row 와의 거리, 두 노드를 변수인 edge에 담습니다. 이후 edge를 원소로 갖는 리스트인 edges에 edge를 append 합니다. (정렬할 때 기존 노드의 index가 바뀌므로, 노드 번호도 저장해야 합니다.)

 

예를 들어 x를 기준으로 정렬하면 2번 노드와 가장 가까운 거리에 있는 노드는 바로 다음에 있는 3번 노드 입니다. (2번과 0번, 2번과 1번, 2번과 4번 노드를 볼 필요가 없습니다.) 따라서 edge에 distance(=11), node1(=2), node2(=3) 정보를 차례 대로 담아 edges에 append합니다. 이렇게 y,z로도 반복하여 edges를 완성합니다. 그 다음으로 edges를 정렬하여 두 노드간 최소 거리인 행성부터 최소 신장 트리를 시작합니다.

x 기준 정렬일 때 2와 3이 가장 가깝고, z 기준 정렬일 때도 2와 3이 가장 가깝습니다. 그러나 거리가 다른데, x일 때 거리는 11 이고 z일 때 거리는 4입니다. edges가 완성되어 정렬하면 (4,2,3) 가 (11,2,3) 보다 앞서게 되고 앞의 (4,2,3) 에서 2,3이 union되면 뒤에 오는 (11,2,3) 에서 2,3은 union처리가 되지 않으므로 가까운 행성이 축별로 중복이 되어도 문제 없습니다.

 

Code

import copy
import sys

input = sys.stdin.readline
def find_parent(parent,x):
    if x != parent[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())
planet = []
for i in range(n):
    planet.append( (i,)+ tuple( map(int,input().split())) )

planet_x = copy.deepcopy(planet)
planet_y = copy.deepcopy(planet)
planet_z = copy.deepcopy(planet)

planet_x.sort(key = lambda x : x[1])
planet_y.sort(key = lambda x : x[2])
planet_z.sort(key = lambda x : x[3])

edges = []
# edge = ( distance, node1, node2 )
for i in range(len(planet_x)-1):
    edge = ( abs(planet_x[i+1][1] - planet_x[i][1]) , planet_x[i][0] , planet_x[i+1][0]  )  
    edges.append( edge )
    
for i in range(len(planet_y)-1):
    edge = ( abs(planet_y[i+1][2] - planet_y[i][2]) , planet_y[i][0] , planet_y[i+1][0]  )  
    edges.append( edge )
    
for i in range(len(planet_z)-1):
    edge = ( abs(planet_z[i+1][3] - planet_z[i][3]) , planet_z[i][0] , planet_z[i+1][0]  )  
    edges.append( edge )

edges.sort()

parent = [0] * n
for i in range(n):
    parent[i] = i

total_distance = 0
for edge in edges:
    distance, a,b  = edge
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        total_distance += distance

print(total_distance)