# Chap 18. 그래프이론 - Q44. 행성 터널

- Author: @mildsalmon
- Published: 2021-12-02
- Updated: 2021-12-05
- Source: http://blex.me/@mildsalmon/chap-18-%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%B4%EB%A1%A0-q44-%ED%96%89%EC%84%B1-%ED%84%B0%EB%84%90
- Tags: 파이썬, 알고리즘, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 백준, 크루스칼알고

---

# 1. 행성 터널

- 난이도
	- 중
- 풀이 시간
	- 40분
- 시간 제한
	- 1초
- 메모리 제한
	- 128MB
- 출처
	- [2887번: 행성 터널 (acmicpc.net)](https://www.acmicpc.net/problem/2887)

### A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

### B. 💡 내 답안

##### a. 😅 1차 시도 (실패 - 메모리 오류)

```python

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[a] = b
    else:
        parent[b] = a

n = int(input())

planets = []
tunnels = []
parent = [i for i in range(n)]
total_cost = 0

for i in range(n):
    x_a, y_a, z_a = list(map(int, input().split()))

    if i >= 1:
        for j in range(len(planets)):
            x_b, y_b, z_b = planets[j]

            cost = min(abs(x_a - x_b), abs(y_a - y_b), abs(z_a - z_b))
            tunnels.append((cost, i, j))

    planets.append((x_a, y_a, z_a))

tunnels.sort()

for tunnel in tunnels:
    cost, a, b = tunnel

    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        total_cost += cost

print(total_cost)

```

##### b. 😊 2차 시도 (성공)

```python

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[a] = b
    else:
        parent[b] = a

n = int(input())

planets_x = []
planets_y = []
planets_z = []
tunnels = []
parent = [i for i in range(n)]
total_cost = 0

for i in range(n):
    x, y, z = list(map(int, input().split()))

    planets_x.append((x, i))
    planets_y.append((y, i))
    planets_z.append((z, i))

planets_x.sort()
planets_y.sort()
planets_z.sort()

for i in range(n-1):
    tunnels.append((planets_x[i+1][0] - planets_x[i][0], planets_x[i][1], planets_x[i+1][1]))
    tunnels.append((planets_y[i+1][0] - planets_y[i][0], planets_y[i][1], planets_y[i+1][1]))
    tunnels.append((planets_z[i+1][0] - planets_z[i][0], planets_z[i][1], planets_z[i+1][1]))

tunnels.sort()

for tunnel in tunnels:
    cost, a, b = tunnel

    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        total_cost += cost

print(total_cost)

```

##### c. 🙄 회고

> 내 풀이

- 쉽게 생각했다.
	- 새로운 행성이 들어오면, 이전에 들어온 행성들과의 거리를 구한 다음, 그 중 최솟값을 저장하는 방식으로 1차 시도를 했었다.

![](https://static.blex.me/images/content/2021/12/2//2021_12_2_15_Es7INE8d3I2qTqaz8KKW.jpg)

- 그러면, 위와 같은 방식으로 계산되는데, 이 경우 간선의 개수가 (n(n+1)/2)개 나온다.
	- 그러나, 문제에서 제시된 행성의 최대 개수가 100,000개이므로, 메모리 초과, 시간 초과가 발생한다.

> 반성

- 단순히 알고리즘만 떠올리고 제약조건을 확인하지 못했다.

> 결론

- 제약조건들도 고려를 해보자.

### C. 🧐 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

x, y, z 좌표가 아래와 같이 주어진다고 생각해보자.

![](https://static.blex.me/images/content/2021/12/2//2021_12_2_15_AoykAB9UjjexXi1o1dBp.jpg)

위의 회고에서 x, y, z를 한꺼번에 계산하는 방식을 시도했다가 실패했으니, 이번에는 각 좌표에서 x, y, z를 따로 분리해서 생각해보자.

![](https://static.blex.me/images/content/2021/12/2//2021_12_2_15_3fX9UlTnJDPGBk0edfAO.jpg)

분리된 x좌표를 정렬하면 아래와 같다.

![](https://static.blex.me/images/content/2021/12/2//2021_12_2_15_C84jIiPF3u3IQVD82jdk.jpg)

이때, 각 좌표는 선형적으로 존재하므로, `i+1 - i`가 각 좌표 사이의 최소거리가 된다.

이렇게 (n-1)번의 연산만으로 각 좌표 사이의 최소 거리를 구할 수 있다. 이제 나머지 y, z를 이런 방식으로 구하면, `3*(n-1)`이 된다.

이제 회고에서 푼 방식의 코드와 문제 해설에서 설명하는 코드를 비교하면서 시간복잡도를 계산해보자.

##### 1) 회고에서 푼 방식

```python

for i in range(n):  
    x_a, y_a, z_a = list(map(int, input().split()))  
  
    if i >= 1:  
        for j in range(len(planets)):  
            x_b, y_b, z_b = planets[j]  
  
            cost = min(abs(x_a - x_b), abs(y_a - y_b), abs(z_a - z_b))  
            tunnels.append((cost, i, j))  
  
    planets.append((x_a, y_a, z_a))
	
```

시간복잡도가 O($n^2$)이다.

##### 2) 문제 해설에서 설명한 방식

```python

for i in range(n):
    x, y, z = list(map(int, input().split()))

    planets_x.append((x, i))
    planets_y.append((y, i))
    planets_z.append((z, i))

planets_x.sort()
planets_y.sort()
planets_z.sort()

for i in range(n-1):
    tunnels.append((planets_x[i+1][0] - planets_x[i][0], planets_x[i][1], planets_x[i+1][1]))
    tunnels.append((planets_y[i+1][0] - planets_y[i][0], planets_y[i][1], planets_y[i+1][1]))
    tunnels.append((planets_z[i+1][0] - planets_z[i][0], planets_z[i][1], planets_z[i+1][1]))
	
```

- 처음 for문
	- O(3\*n)
- 밑에 planets_x 정렬 부분
	- O(3\*nlogn) 
- 두번째 for문
	- O(3\*(n-1))

즉, O(n) + O(nlogn) + O(n)으로 O($n^2$)보다 작은 것을 알 수 있다.

##### a. 책 답안

[python-for-coding-test/4.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/18/4.py)

# 참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] [baekjoon](https://www.acmicpc.net/user/baekjoon). [2887번: 행성 터널 (acmicpc.net)](https://www.acmicpc.net/problem/2887). Baekjoon. (accessed Dec 5, 2021)