백준/ Platinum 5 문제 , 백준 파이썬 2887, 행성 터널 [최소 스패닝 트리, 프림 알고리즘]

백준/ Platinum 5 문제 , 백준 파이썬 2887, 행성 터널 [최소 스패닝 트리, 프림 알고리즘]

 

 

 

풀이 시간

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
기본 프림 알고리즘으로는 시간 복잡도가 O(N^2) 가 발생하여 메모리 초과가 났다.
저장할 간선의 갯수를 줄이는 것이 관건인데, 좌표들을 x,y,z 오름차순으로 각각 세번 나누어서 정렬하여  인접한 노드들끼리의 간선들 가중치를 확인한다. 인접한다는 것은 문제에서 요구하는 최소의 가중치를 가질 확률이 높으므로 배열에 저장해두고 이것들만 가지고도 최소 신장트리를 만들수 있다. 이렇게 할때 시간 복잡도는 O(3*N) 으로 이전보다 확 줄게되어 메모리 초과가 발생하지 않는다.

 

 

 

문제 출처

https://www.acmicpc.net/problem/2887

2887번: 행성 터널

 

 

 

풀이

 

 

각각 x / y / z 를 기준으로 오름 차순 정렬을 한다.

 

이후 N-1 개의 인접 간선들을 graph 배열에 양방향으로 저장한다.

 

이 저장된 값들 중에서도 이제 최소 가중치를 가진 것들을 우선적으로 이어 전체 경로를 설정한다.

 

 

 

 

 

정답

 

 

import heapq
import sys
input=sys.stdin.readline

N=int(input())
planets=[[] for _ in range(N+1)]
for i in range(1,N+1):
    planets[i]=list(map(int,input().split()))
    planets[i]+=[i]
planets[0]=[sys.maxsize,sys.maxsize,sys.maxsize,0]
    
visited=[True,True]+[False]*(N-1)
graph=[[] for _ in range(N+1)]

for i in range(3):
    planets.sort(key=lambda x:x[i])
    for j in range(1,N):
        a,b,c,d=planets[j-1]
        A,B,C,D=planets[j]
        graph[d].append((min(abs(a-A),abs(b-B),abs(c-C)),D))
        graph[D].append((min(abs(a-A),abs(b-B),abs(c-C)),d))
    
q=graph[1]
heapq.heapify(q)
result=0

while q:
    Z,X=heapq.heappop(q)
    if not visited[X]:
        result+=Z
        visited[X]=True
        for i in graph[X]:
            if not visited[i[1]]:
                heapq.heappush(q,i)

print(result)