728x90
✅ 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)
728x90
'코딩테스트 > 그래프(MST(쿠루스칼,프림),위상정렬)' 카테고리의 다른 글
[위상정렬] (백준_2252) 줄세우기 - 파이썬 (다시 풀 문제는 아님) (1) | 2024.09.07 |
---|---|
[그래프] 위상정렬 이론 (1) | 2024.09.04 |
[그래프] MST(쿠루스칼, 프림) 이론 (3) | 2024.09.04 |