[Python] 2887 - 행성 터널

[Platinum V] 행성 터널 - 2887 

[문제 링크](https://www.acmicpc.net/problem/2887)

🗝️알고리즘 분류

• 그래프 탐색
• 최소 스패닝 트리

---

💻문제 정의

3차원 좌표 위의 한 점은 행성의 위치이다. 이때 각 행성 사이의 터널을 연결할 때, 필요한 최소 비용을 구하는 프로그램을 작성하는 문제이다.

 

💡접근 및 설계

최소 스패닝 트리를 이용하여 최소 비용 트리를 구현하였다. Union-Find 방식을 이용하여 트리를 간단하게 구현할 수 있다.

def get_parent(x):
    if (parent[x] == x):
        return x

    parent[x] = get_parent(parent[x])

    return parent[x]

def union_parent(a, b):
    a = get_parent(a)
    b = get_parent(b)

    if (a < b):
        parent[b] = a

    else:
        parent[a] = b

def same_parent(a, b):
    return get_parent(a) == get_parent(b)

 

✏️알고리즘 풀이

tree = []

# 각 차원(x, y, z)에 대해
for dim in range(3):
    # 해당 축에 대해 정렬: (좌표값, 노드번호)
    sorted_pos = sorted([(position[i][dim], i) for i in range(1, N+1)])

    # 인접한 노드끼리 간선 연결
    for i in range(N - 1):
        a_idx = sorted_pos[i][1]
        b_idx = sorted_pos[i + 1][1]
        weight = abs(sorted_pos[i][0] - sorted_pos[i + 1][0])
        tree.append([a_idx, b_idx, weight])

문제에선 3차원의 좌표가 주어진다. 두 점의 거리는 x, y, z 좌표의 각각의 차들 중 최솟값이다. 

축을 기준으로 정렬 후, 인접한 점들끼리 간선을 이어 트리를 구성한다.

 

N=5일때, 한 축당 간선 4개 * 3축으로 총 12개의 간선으로 이루어진 트리가 완성된다.

 

## 실패 코드 (메모리 초과)

tree = []
for i in range(1, N):
    for j in range(2, N+1):
        if (i == j):
            continue
        x = abs(position[i][0] - position[j][0])
        y = abs(position[i][1] - position[j][1])
        z = abs(position[i][2] - position[j][2])
        weight = min(x, y, z)

        tree.append([i, j, weight])

처음에는 단순무식하게 모든 좌표에 대해서 최솟값을 weight로 두어 간선을 구성하였으나, N의 범위는 최대 10만으로 간선의 수는 최대 5,000,000,000개가 될 수 있다.

 

따라서 간선의 추가 방식에서 최적화가 필요하였다.

 

🗒️제출 코드

# 2887 행성 터널

N = int(input())

position = [[]]
for _ in range(N):
    x, y, z = map(int, input().split())
    position.append([x, y, z])

tree = []

# 각 차원(x, y, z)에 대해
for dim in range(3):
    # 해당 축에 대해 정렬: (좌표값, 노드번호)
    sorted_pos = sorted([(position[i][dim], i) for i in range(1, N+1)])

    # 인접한 노드끼리 간선 연결
    for i in range(N - 1):
        a_idx = sorted_pos[i][1]
        b_idx = sorted_pos[i + 1][1]
        weight = abs(sorted_pos[i][0] - sorted_pos[i + 1][0])
        tree.append([a_idx, b_idx, weight])

tree.sort(key = lambda x : x[2])

parent = [i for i in range(N+1)]

def get_parent(x):
    if (parent[x] == x):
        return x

    parent[x] = get_parent(parent[x])

    return parent[x]

def union_parent(a, b):
    a = get_parent(a)
    b = get_parent(b)

    if (a < b):
        parent[b] = a

    else:
        parent[a] = b

def same_parent(a, b):
    return get_parent(a) == get_parent(b)

answer = 0
for a, b, cost in tree:
    if not (same_parent(a, b)):
        union_parent(a, b)
        answer += cost

print(answer)

---

💭오늘의 회고

처음으로 풀어본 플래티넘 문제이다.

 

확실히 지금까지의 문제와는 다르게, 시간 복잡도나 메모리 관련해서 조금 더 신경을 많이 써야겠다는 생각을 하였다.

문제 구현 난이도 자체는 크게 달라진 바 없으나, 해당 문제처럼 단순 반복에서 메모리 관리를 해주어야 한다는 것을 깨달았고, 그에맞게 더욱 효율적인 알고리즘을 선택해야 한다는 것을 배웠다.

 

갈 길이 아직 멀다...