백준 2887 행성 터널 (Python)

문제 링크

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

2887번: 행성 터널

---

Test Case

---

문제 풀이

처음에는 단순한 크루스칼 문제로 풀면 될줄 알았는데, N 조건을 보면 최대 100,000이기 때문에 모든 노드를 연결하는 경우의 수인 N(N-1)/2개를 다 계산하면 시간초과가 나온다. 따라서 다른 방법으로 두 행성간의 거리를 확인해야 한다.

터널의 비용이 min(X좌표 차, Y좌표차, Z좌표 차)인 점을 생각해서, 주어진 각 좌표를 X,Y,Z 각 축에 대하여 오름차순 정렬하여 각 간선의 거리를 구해서 edges 리스트에 넣은 뒤 최소 신장트리를 만든다.

처음에 모든 노드를 연결해야하는 경우의 수만 구현하면 쉽게 풀수 있다는 생각에 문제 조건을 충분히 고려하지 않고 신나게 풀었는데, 풀고 답을 보고 나서 살짝 힘이 빠졌다. 아는거 나왔다고 흥분하지말고 한번 더 심호흡 하고 풀자. 마지막에 print(cost)를 계속해서 삽질한건 비밀

이제 그래프 문제는 어려운 문제 빼고 끝. 최단 경로 문제 풀이 시작

---

Source Code

틀린 풀이

planet = []
for i in range(n):
    x,y,z = map(int, input().split())
    planet.append((x,y,z))

edges = []
for i in range(n):
    for j in range(i+1,n):
        cost = min(abs(planet[i][0]-planet[j][0]), abs(planet[i][1]-planet[j][1]), abs(planet[i][2]-planet[j][2]))
        edges.append((cost,i,j))

 

맞은 풀이

import sys
input = sys.stdin.readline

# 행성 : n
n = int(input())

def find_parent(parent,x):
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
    if a < b:
        parent[b] = a
    else :
        parent[a] = b

parent = [0] * (n+1)
for i in range(1,n+1):
    parent[i] = i


x = []
y = []
z = []

for i in range(1, n+1):
    data = list(map(int, input().split()))
    x.append((data[0], i))
    y.append((data[1], i))
    z.append((data[2], i))

x.sort()
y.sort()
z.sort()

edges = []
for i in range(n-1):
    edges.append((x[i+1][0] - x[i][0], x[i][1], x[i+1][1]))
    edges.append((y[i+1][0] - y[i][0], y[i][1], y[i+1][1]))
    edges.append((z[i+1][0] - z[i][0], z[i][1], z[i+1][1]))

edges.sort()

result = 0
for edge in edges:
    cost,a,b = edge
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        result += cost
        
print(result)