[Python]최소신장트리 백준 2887

 문제

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

먼저 3차원의 좌표를 준다.그런데 행성의 개수가 10만개까지 주어진다.

모든 간선을 구하게 되면 메모리초과와 시간초과를 볼수 있을것이다.

먼저  모든 경로를 구해서 최소신장트리를 구해보았다.

import sys
 
#크루스칼에 필요한 유니온 파인드
def Find(x):
    if p[x]==x:
        return x
    else:
        y=Find(p[x])
        p[x]=y
        return y
 
def Union(x,y):
    x=Find(x)
    y=Find(y)
    if x!=y:
        p[y]=x
 
 
N=int(sys.stdin.readline())
s_location=[]
p=[i for i in range(N)]
e=[]
for i in range(N):
    x,y,z=map(int,sys.stdin.readline().split())
    s_location.append([x,y,z])
 
 
for i in range(N-1):
    for j in range(i+1,N):
        #모든 경우의 간선을 구해준다.
        x=abs(s_location[i][0]-s_location[j][0])
        y=abs(s_location[i][1]-s_location[j][1])
        z=abs(s_location[i][2]-s_location[j][2])
        e.append([min(x,y,z),i,j])
 
#크루스칼 알고리즘
e.sort(key=lambda x:x[0])#거리를 기준으로 정렬
count=0
result=0
for dis,s,e in e:
    if Find(s)!=Find(e):
        result+=dis
        Union(s,e)
    if count==N-1:
        break
 
print(result)
 

이렇게 구하면 메모리 초과가 난다.

물론 메모리 제한에 걸리지 않아도 시간초과가 될것이다.

핵심은 간선의 개수를 줄이는 것이다.

모든 간선이 아닌 각 좌표별로 거리를 구하면 간선의 개수를 현저히 줄일수있다.

기존 방식은 V*(V-1)/2의 간선을 추가한다.

좌표별로 구하게 되면 E를 3*(V-1)로 줄일수있다.

각 좌표를 기준으로 오름차순 정렬을 했을때 X1->X2가 X1->X3보다 클수는 없기

때문에 V-1개의 간선이 나온다.

각 좌표별로 V-1의 간선이 나오며 3차원 좌표임으로 3*(V-1)의 간선이 나오게 된다.

import sys
#크루스칼에 필요한 유니온 파인드
def Find(x):
    if p[x]==x:
        return x
    else:
        y=Find(p[x])
        p[x]=y
        return y
 
def Union(x,y):
    x=Find(x)
    y=Find(y)
    if x!=y:
        p[y]=x
 
N=int(sys.stdin.readline())
s_location=[]
p=[i for i in range(N)]
e=[]
for i in range(N):
    x,y,z=map(int,sys.stdin.readline().split())
    s_location.append([x,y,z,i])#x,y,z좌표 i번째노드
 
for j in range(3):
    s_location.sort(key=lambda x:x[j])#각 좌표별로 정렬
    before_location=s_location[0][3]
    for i in range(1,N):#각 좌표별로 간선추가
        cur_location=s_location[i][3]
        e.append([abs(s_location[i][j]-s_location[i-1][j]),before_location,cur_location])
        before_location=cur_location
 
 
e.sort(key=lambda x:x[0])
 
#크루스칼 알고리즘
count=0
result=0
for dis,start,end in e:
    if Find(start)!=Find(end):
        result+=dis
 
        Union(start,end)
    if count==N-1:
        break
 
print(result)