[이코테] 그래프 알고리즘 - 행성 터널

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

2887번: 행성 터널

사고과정

• 최소 신장 트리를 만드는 크루스칼 알고리즘을 활용하는 거라고 생각했다. 그런데 문제에서 간선 비용을 계산하는 문제가 또 있었는데 그것을 해결하지 못했다..심지어 책 속에 문제가 잘못되어 있어서 더 시행착오를 거친 듯하다..하하.. 책에서는 거리 계산할 때 |Y_A-X_B| 라고 되어 있는데 X_B를 Y_B로 고쳐야 한다..
• 특이한 점은 임의의 두 노드 사이를 모두 측정하면 총 연산횟수가 50억이되어 시간초과가 된다. 따라서 주어진 거리 계산 공식을 활용해서 시간 초과를 해결해야 하는데, 계산 공식을 살펴보면 x,y,z 중 아무 축이나 선택해서 그 축을 기준으로 거리를 계산해서 정렬한 것만을 가지고 최소 신장 트리를 만들 수 있다. 그렇게 되면 탐색해야 할 간선 정보가 기하급수적으로 감소한다.. 이렇게 최적의 솔루션이라고 판단하는 것을 어떻게 하는건지...아직까지는 잘 모르겠으나.. 모든 간선 정보를 탐색하게 되면 시간초과 문제가 발생한다는 것을 캐치하면 계산 공식을 가지고 활용할 수도 있을 것 같다.. 매우 어려운 듯 하다.. 그래서 결국 x, y, z 축의 값 별로 각각 리스트에 담고 정렬한 후, 각 축의 좌표끼리 거리 계산을 한 후 간선 비용 정보에 담은 후 이번엔 거리(간선 비용)를 기준으로 오름차순 정렬한다. 그리고 간선 하나씩 확인하면서 크루스칼 알고리즘을 활용하면 된다..
• 역시 백준 문제는 아직 내 힘으로는 무리데스..

풀이(스스로 못 푼 풀이)

n = int(input())
# 부모 테이블
parent = [0] * (n+1)
for i in range(1, n+1):
    parent[i] = i

# find, union 연산
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: # b -> a로 연결
        parent[b] = a
    else:
        parent[a] = b

# 각 행성의 좌표 입력받기
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][1], x[i][1]))
    edges.append((y[i+1][0]-y[i][0], y[i+1][1], y[i][1]))
    edges.append((z[i+1][0]-z[i][0], z[i+1][1], z[i][1]))
# 이번엔 간선 비용 순으로 정렬
edges.sort()
result = 0
for edge in edges:
    cost, a, b = edge
    if find_parent(parent, a) != find_parent(parent, b):
        result += cost
        union_parent(parent, a, b)

print(result)