백준 2887 : 행성 터널 (Python)

본문 링크

import sys
input=sys.stdin.readline

"""
두 수의 차의 절대값이므로 좌표값이 가장 비슷한걸 찾자.
x,y,z 에 대해서 따로 정렬해서 따로 구해주면
최적의 해를 찾지 못한다. 

따라서 배열 3개를 써보자.

"""
def Find(x):

    if x!=disjoint[x]:
        disjoint[x]=Find(disjoint[x])

    return disjoint[x]

N=int(input())

disjoint=[ _ for _ in range(N+1) ] ; answer=0

SVEMIR=[]

X=[]
Y=[]
Z=[]
for i in range(N):
    a,b,c=map(int,input().split())
    X.append((a,i))
    Y.append((b,i))
    Z.append((c,i))

X.sort(key=lambda x:x[0])
Y.sort(key=lambda x:x[0])
Z.sort(key=lambda x:x[0])

edge=[]

for i in range(1,N):
    edge.append((abs(X[i][0]-X[i-1][0]),X[i][1] , X[i-1][1] ) )
    edge.append((abs(Y[i][0]-Y[i-1][0]),Y[i][1] , Y[i-1][1] ) )
    edge.append((abs(Z[i][0]-Z[i-1][0]),Z[i][1],  Z[i-1][1] ) )

edge.sort()
for value,x,y in edge:

    x=Find(x)
    y=Find(y)

    if x!=y:
        if x>y:
            disjoint[x]=y
        else:
            disjoint[y]=x
        answer+=value

print(answer)

📌 어떻게 접근할 것인가?

• 두 행성 $A(x_A, y_A, z_A)$ 와 $B(x_B, y_B, z_B)$ 를 터널로 연결할 때 드는 비용은 $min(|x_A-x_B|, |y_A-y_B|, |z_A-z_B|)$ 이다.

이 문제의 가장 핵심이 되는 부분입니다.

절대값이 작아야 한다는 것은 두 수가 비슷해야한다는 점입니다.

즉 , $X$, $Y$ , $Z$ 좌표에 대해 정렬을 하면 인접한 두 정점끼리의 차는 최소가 될 수 있다.

따라서 $X$, $Y$ , $Z$ 에 대한 리스트와 값을 입력받고 그때의 번호도 입력받은 후에 좌표값에 대해 정렬은 한다.

이후 edge 리스트에서

• $abs(X[i][0]-X[i-1][0])$, $abs(Y[i][0]-Y[i-1][0]),Y[i][1]$ , $abs(Z[i][0]-Z[i-1][0]),Z[i][1]$

인접한 두 정점의 절대값을 추가해주고

• $X[i-1][1]$ , $Y[i-1][1]$ , $Z[i-1][1]$

인덱스 값을 넣습니다.

이후 edge.sort , 가중치에 대해 정렬하고 가중치가 작은 순서대로 크루스칼 알고리즘을 사용해줍니다.