# Chap 18. 그래프이론 - Q43. 어두운 길

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

---

# 1. 어두운 길

- 난이도
	- 중
- 풀이 시간
	- 40분
- 시간 제한
	- 1초
- 메모리 제한
	- 128MB
- 출처
	- University of Ulm Local Contest

### A. 📜 문제

한 마을은 N개의 집과 M개의 도로로 구성되어 있다. 각 집은 0번부터 N-1번까지의 번호로 구분된다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일하다. 

정부에서 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 한다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 한다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하라.

##### a. 예를 들면. 

예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 하면, 하루 동안 이 가로등을 켜기 위한 비용은 7이다.

##### b. 입력 조건

- 첫째 줄에 집의 수 N (1 <= N <= 200,000)과 도로의 수 M (N-1 <= M <= 200,000)이 주어진다.
- 다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X, Y, Z가 주어지며, 공백으로 구분한다. (0 <= X, Y < N) 이는 X번 집과 Y번 집 사이에 양방향 도로가 있으며, 그 길이가 Z라는 의미이다. 단, X와 Y가 동일한 경우는 없으며 마을을 구성하는 모든 도로의 길이 합은 $2^31$보다 작다.

##### c. 출력 조건

- 첫째 줄에 일부 가로등을 비활서오하하여 절약할 수 있는 최대 금액을 출력하라.

##### d. 테스트 케이스

- 입력 예시

	```

	7 11
	0 1 7
	0 3 5
	1 2 8
	1 3 9
	1 4 7
	2 4 5
	3 4 15
	3 5 6
	4 5 8
	4 6 9
	5 6 11

	```

- 출력 예시

	```

	51

	```
	
### B. 💡 내 답안

##### a. 😊 1차 시도 (성공)

```python

"""
Date    : 2021.12.01
Update  : 2021.12.01
Source  : Q43_어두운 길.py
Purpose : 크루스칼 알고리즘 적용하여 해결.
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""
# 각 집 사이의 거리가 최소인 길만 가로등을 켠다. -> 크루스칼 알고리즘
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
    elif a < b:
        parent[b] = a

n, m = list(map(int, input().split()))

roots = []
# 집의 번호가 0 ~ N-1번으로 주어졌기 때문에 parent의 원소 갯수를 n개만 생성함.
parent = [0] * n
save_cost = 0

for _ in range(m):
    x, y, z = list(map(int, input().split()))
    # 크루스칼 알고리즘을 사용하기 위해(비용 순으로 정렬하기 위해), 길에 대한 정보를 바꿔서 roots 리스트에 집어넣음.
    roots.append((z, x, y))
# 최소 비용의 길부터 탐색하기 위해 첫번째 원소를 기준으로 정렬을 함.
roots.sort()

# 초기 각 집의 부모를 자기 자신으로 초기화함.
for i in range(1, n):
    parent[i] = i

for root in roots:
    cost, a, b = root
    # 부모가 같지 않다면(싸이클이 없다면) union 연산을 함.
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
    else:
        # 문제에서 구하고자 하는 값이 가로등을 비활성하여 절약할 수 있는 금액임.
        # 따라서 가로등을 켜지 않는 경우를 누적하여 합함.
        save_cost += cost

print(save_cost)

```

##### c. 🙄 회고

> 내 풀이

- 크루스칼 알고리즘이 떠올라서 적용하였다.

### C. 🧐 문제 해설

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

각 노드(집)들 사이의 길은 이런 방식으로 활성화되고 배제된다.

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

##### a. 책 답안

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

# 참고문헌

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