[그래프 이론] 행성터널

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간:  20분 + a

1. 문제 설명

- 3차원의 행성의 좌표가 주어지며, 각 행성을 연결하는 도로를 최소한의 비용으로 짓고자 한다. 이때 각 행성을 연결할 수 있는 최소 비용은 얼마인지를 묻는 문제

2. 접근 방식

- 각 행성의 좌표를 X축, Y축, Z축끼리만 따로 계산한다.

- 그리고 각 행성의 거리에 대한 계산 정보를 X, Y, Z축 모두 계산해서 하나의 리스트에 넣고 정렬을 수행한다.

- 각 거리에 대한 계산정보가 담긴 리스트를 돌면서 사이클이 발생하지 않을 때만 집합 연산을 수행한다. (이렇게 하면 X, Y, Z축 우선 순위에 상관없이 비용이 낮은 것이 제일 우선적으로 연결된다. )

3. 코드

n = int(input())

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

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 = list(range(n))

## x, y, z축 입력받기
x_ls = []
y_ls = []
z_ls = []

for i in range(n):
    x, y, z = map(int, input().split())
    x_ls.append((x, i))
    y_ls.append((y, i))
    z_ls.append((z, i))
    
x_ls.sort()
y_ls.sort()
z_ls.sort()

## 3*(n-1)의 간선 입력으로 받기
edges = []
for i in range(n-1):
    # cost, a, b
    edges.append((abs(x_ls[i][0]-x_ls[i+1][0]), x_ls[i][1], x_ls[i+1][1]))
    edges.append((abs(y_ls[i][0]-y_ls[i+1][0]), y_ls[i][1], y_ls[i+1][1]))
    edges.append((abs(z_ls[i][0]-z_ls[i+1][0]), z_ls[i][1], z_ls[i+1][1]))
edges.sort()

# 간선을 돌면서 check
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)

4. 코멘트

- 처음에 X, Y, Z 축으로 나눠서 계산을 하면 될 거 같다는 생각을 했었다. 하지만, 해당 거리 정보를 어떻게 노드 정보와 연결시킬까에 대한 부분으로 더 넘어가지 못했었다.

- X, Y, Z축 입력을 받을 때, 해당 리스트에 거리정보와 노드 정보를 '튜플'로 보내는 기법과 각 노드에 대한 거리 정보를 하나의 리스트(edges)에 넣어서 비용이 낮은 순서대로 살펴보는 기법을 배웠다.