Home 백준 - 2887. 행성터널(MJ)
Post
Cancel

백준 - 2887. 행성터널(MJ)

Posted Dec 19, 2022 Updated Jan 29, 2023
By MINJEONG KIM
14 min read

#2887. 행성터널

백준사이트의 플래티넘 5티어 문제이다.

📖Description

2887_%EB%AC%B8%EC%A0%9C 2887_%EC%9E%85%EC%B6%9C%EB%A0%A5

우주에 있는 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(xA-xB,yA-yB,zA-zB)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.

1
2
3
4
5
6
7

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

1

4

🔍Process

Algorithm

최소 스패닝 트리 문제 → 크루스칼 알고리즘 사용

Spanning Tree

  • 스패닝 트리 (Spanning Tree) = 신장 트리
    • 그래프의 최소 연결 부분 그래프이다.
      • 최소 연결 : 간선의 수가 가장 적다
      • n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 Spanning Tree가 된다.
    • 즉, 그래프에서 일부 간선을 선택해서 만든 트리이다.
  • DFS, BFS를 이용해 그래프에서 신장 트리를 찾을 수 있다.
    • 탐색 도중에 사용된 간선만 모으면 만들 수 있다.
  • 하나의 그래프에는 많은 신장 트리가 존재할 수 있다.
  • Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.
  • 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결 한다. Untitled 1

MST(Miminum Spanning Tree); 최소 신장 트리

  • Spanning Tree중에서 사용된 간선들의 가중치 합이 최소인 트리
  • 즉, 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.
  • 특징
    • 간선의 가중치 합이 최소여야 한다.
    • n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
    • 사이클이 포함되어서는 안된다.

MST 구현 방법 (Kruskal MST, Prim MST)

  1. 크루스칼 알고리즘

탐욕적인 방법(greedy method) 을 이용하여 네트워크(가중치를 간선에 할당한 그래프)의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

  • 탐욕적인 방법
    • 결정을 해야 할 때마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것
    • 탐욕적인 방법은 그 순간에는 최적이지만, 전체적인 관점에서 최적이라는 보장이 없기 때문에 반드시 검증해야 한다.
    • 다행히 Kruskal 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다.
  • MST(최소 비용 신장 트리) 가 1) 최소 비용의 간선으로 구성됨 2) 사이클을 포함하지 않음 의 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택 한다.
  • 동작과정
    • 간선 선택 기반 알고리즘
    • 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택하는 방법

Untitled

  • 주의!
    • 다음 간선을 이미 선택한 간선들의 집합에 추가할 때는 사이클을 생성하는지를 체크
    • 새로운 간선이 이미 다른 경로에
    • 사이클 생성 여부를 확인하는 방법
      • union-find 알고리즘 이용
        • find : 각 노드의 부모노드 찾기
        • union : 부모자신간의 노드 관계 형성

Approach

이 문제는 크루스칼 알고리즘을 구현하는 문제이다.

위에서도 설명했듯이 크루스칼 알고리즘은 각 정점 간 간선의 가중치를 작은 순서대로 선택해나간다. union-find 연산으로 싸이클이 발생하는지 여부를 판단하여 선택하며 구현하면 된다.

여기서 선택의 대상인 간선의 가중치 값은 문제에서 주어진 각 행성들 간의 x, y, z 좌포 차이 중 최소값이 된다.

즉, 문제에서 간선의 가중치가 될 수 있는 값을 찾아놓아야 최소도 구할 수 있으므로 이를 구하는 것이 핵심이다.

처음에는 모든 행성들 간에 서로 X, Y, Z 좌표값 차이를 구해서 간선의 가중치 정보로 넣는 방법을 생각할 수 있지만, 이 문제에서는 행성이 최대 10만개 주어지므로 대략 10만*10만 만큼의 비교 및 데이터가 발생합니다. 따라서 메모리 초과 문제가 발생할 수 있습니다.

어차피 행성들 간의 X, Y, Z 좌표값 차이 중 가장 작은 값들이 간선 가중치 후보가 될 수 있는 것이므로 아래와 같은 방법을 생각할 수 있습니다.

  • 각 행성들의 X,Y,Z 좌표를 별도로 벡터에 담아두고 오름차순 정렬해 놓는다.
  • X 좌표를 우선 예로 들면, 행성 A. B, C, D 의 X좌표가 각각 11, 3, 2, 8 이었을 경우 오름차순 정렬하면 2, 3, 8, 11 이며, 각각 C, B, D, A 순이다.
  • 따라서 행성 C-B, B-D, D-A 로 연결될 때 각각의 X좌표 차이(3-2, 8-3, 11-8)가 행성들 간 X좌표 차이의 최솟값이 된다.
  • 즉, 행성 C는 B와 연결될 때 X좌표 차이가 가장 작으며, 행성 B는 행성 D와 연결될 때 X좌표 차이가 가장 작다.
  • Y, Z 좌표에도 위와 똑같은 방법을 적용한다. 그리고 구해진 X, Y, Z 좌표 차이의 최솟값들 모음을 가지고 크루스칼 알고리즘을 진행한다.

My submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

n = int(input())
planet_x, planet_y, planet_z = [], [], []

# 0. x, y, z를 각각 입력받는다.
for i in range(n):
    x, y, z = list(map(int, input().split()))
    planet_x.append([i, x])
    planet_y.append([i, y])
    planet_z.append([i, z])

# 1.  x끼리, y끼리, z끼리 정렬한다.
planet_x.sort()
planet_y.sort()
planet_z.sort()

# 2. 최소비용 구하기
diff = []
for i in range(1, n):
	diff.append((abs((planet_x[i][1] - planet_x[i-1][1]), planet_x[i][0], planet_x[i-1][0]))
	diff.append((abs((planet_y[i][1] - planet_y[i-1][1]), planet_y[i][0], planet_y[i-1][0]))
	diff.append((abs((planet_z[i][1] - planet_z[i-1][1]), planet_z[i][0], planet_z[i-1][0]))

diff.sort() #주어진 모든 간선 정보에 대해 낮은 순서로 정렬

# 3. 크루스칼 알고리즘
# find, union이 cycle을 
# cycle이 발생하는 조건이 뭘까? 
def find_parent(planet, x):
	# 부모노드와 자식노드가 같지 않다면 = 부모노드가 따로 있는 의미!
	if planet[x] != x:
		return find_parent(planet, planet[x]) #그 부모노드를 자식으로 하는 또 다른 부모노드를 재귀적으로 탐색
	# 부모노드 = 자식노드 -> 해당 노드 리턴
return x

#union: 부모 자식이 없다 -> 관계가 없다 (즉, 자기 자신을 부모로 갖는다) -> 부모 자식 관계가 없으면, union해서 합쳐줌!(부모자식관계로 만들어줌)
def union_parent(planet, a, b):
# a, b각 부모노드 탐색 -Find 연산
	a = find_parent(planet, a)
	b = find_parent(planet, b)
	#각 부모노드 비교 후 부모-자식관계 형성 - Union연산
	if a < b:
	planet[b] = a
	else:
		planet[a] = b

for cost, a, b in diff:
	union_parent(diff)

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

def find_parent(planet):
    if parent_table[planet] == planet:
        return planet
    else:
        parent_table[planet] = find_parent(parent_table[planet])
        return parent_table[planet]

def union_parent(planet1, planet2):
    parent1 = find_parent(planet1)
    parent2 = find_parent(planet2)

    parent_table[parent2] = parent1

if __name__ == "__main__":
    result = 0

    N = int(sys.stdin.readline())
    planet_location_list = []

    for i in range(N):
        x, y, z = map(int, sys.stdin.readline().split())
        planet_location_list.append([x, y, z, i])

    edge_between_planet_list = []
    for x_y_z in range(3):
        planet_location_list.sort(key=lambda v: v[x_y_z])
        before_location = planet_location_list[0][3]
        for i in range(1, N):
            cur_location = planet_location_list[i][3]
            edge_between_planet_list.append([before_location, cur_location, abs(planet_location_list[i][x_y_z] - planet_location_list[i - 1][x_y_z])])
            before_location = cur_location
    edge_between_planet_list.sort(key=lambda v: v[2])

    parent_table = [i for i in range(N)]
    for planet1, planet2, distance in edge_between_planet_list:
        if find_parent(planet1) != find_parent(planet2):
            result += distance
            union_parent(planet1, planet2)

    print(result)

💡Remenbrance

  • 이 문제 알고보니 실버도 아니고 골드도 아니고 플래티넘 문제였다… 그래서 당연히 어렵고, 내겐 수준 높은 것이 어쩔 수 없다.
  • 혼자서 완전히 풀지는 못했고 다른 분들의 아이디어와 코드를 참고했다. 그랬음에도 불구하고 완벽히 이해하지는 못했다..
  • 새로운 개념, 최소 스패닝 트리와 크루스칼 알고리즘에 대해서 배울 수 있었다.
  • 이 문제의 핵심은 모든 행성이 연결되기만 하면 되고 연결할 때 최소 비용만 구하면 되기 때문에 선택되지도 않을 굉장히 먼 거리의 모든 경우의 수를 다 담을 필요가 없다 → 모든 간선을 넣는 방식을 사용할 시 시간 복잡도 : $O(N^2)$ → 크루스칼 알고리즘 방식을 적용할 시 시간 복잡도 : $O(3N)$

References

BaekJoon, MINJEONG_B
BaekJoon MINJEONG 크루스칼 알고리즘
This post is licensed under CC BY 4.0 by the author.
Recently Updated
Contents

Add-two-Numbers

LeetCode - 1971. Find if Path Exists in Graph (MJ)