[프림] (백준_2887) 행성터널 - 파이썬

✅ X,Y,Z마다 정렬하는게(3번) 힙을 각각 X,Y,Z마다 만들고 빼는것보다 빠름 

정렬 사용) 총 시간 복잡도: O(N) + O(N log N) + O(N) = O(N log N)
힙 사용) 총 시간 복잡도: O(N log N) + O(N log N) + O(N) = O(N log N)

아무래도 힙을 넣는데서 더 오래걸리는 것 같음 

 

✅ 통과 코드 (정렬 사용)

from heapq import heappop,heappush
N = int(input())
hangsungs = [list(map(int,input().split()))+[i] for i in range(N)]


q = []
visited = [0]*(N)
G = [[] for _ in range(N)]

for i in range(3):
    hangsungs.sort(key=lambda x:x[i])
    for a,b in zip(hangsungs,hangsungs[1:]):
        G[a[3]].append((abs(a[i]-b[i]),b[3]))
        G[b[3]].append((abs(a[i]-b[i]),a[3]))

heappush(q,(0,0))
ans = 0
cnt = 0
while cnt < N:
    w,v = heappop(q)
    if visited[v]:
        continue
    visited[v]=1
    ans+=w
    cnt+=1
    for nw,nv in G[v]:
        heappush(q,(nw,nv))
print(ans)

✅ 불통 코드 (힙 사용)

from heapq import heappop,heappush
N = int(input())
X,Y,Z = [],[],[]
for i in range(N):
    x,y,z=map(int,input().split())
    heappush(X,(x,i))
    heappush(Y,(y,i))
    heappush(Z,(z,i))

q = []
visited = [0]*(N)
G = [[] for _ in range(N)]
(bx,bxi),(by,byi),(bz,bzi) = heappop(X),heappop(Y),heappop(Z)
for _ in range(N-1):
    (x,xi),(y,yi),(z,zi) = heappop(X),heappop(Y),heappop(Z)
    G[xi].append((abs(bx-x),bxi))
    G[bxi].append((abs(bx-x),xi))
    G[yi].append((abs(by-y),byi))
    G[byi].append((abs(by-y),yi))    
    G[zi].append((abs(bz-z),bzi))
    G[bzi].append((abs(bz-z),zi))
    bx,bxi,by,byi,bz,bzi = x,xi,y,yi,z,zi

heappush(q,(0,0))
ans = 0
cnt = 0
while cnt < N:
    w,v = heappop(q)
    if visited[v]:
        continue
    visited[v]=1
    ans+=w
    cnt+=1
    for nw,nv in G[v]:
        heappush(q,(nw,nv))
print(ans)