[그래프 이론] 실전 문제 <3> 도시 분할 계획 / 이것이 취업을 위한 코딩테스트다 with 파이썬

도시 분할 계획

난이도 ★★☆  풀이 시간 40분  시간 제한 2초

 

    동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대고 회의 중이었다.

    마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다.

    마을의 이장은 마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.

    그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

 

입력 조건

• 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2 이상 100,000 이하인 정수이고, M 은 1이상 1,000,000 이하인 정수이다.
• 그다음 줄부터 M줄에 걸쳐 길의 정보가 A, B, C 3개의 정수로 공백으로 구분되어 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C(1≤ C ≤ 1,000)라는 뜻이다.

 

출력 조건

• 첫째 줄에 길을 없애고 남은 유지비 합의 최솟값을 출력한다.

 

입력 예시

7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4

출력 예시

8

---

코드

def find_house(parent, x):
    if parent[x] != x:
        parent[x] = find_house(parent, parent[x])
    return parent[x]

def union_house(parent, a, b):
    a = find_house(parent, a)
    b = find_house(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 집 개수, 길 개수
N, M = map(int, input().split())
# 부모 테이블 선언 후 자기 자신으로 초기화
parent = [0] * (N + 1)
for i in range(1, N+1):
    parent[i] = i

# 모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0

# 간선 데이터
for i in range(M):
    A, B, C = map(int, input().split())
    edges.append((C, A, B))
# 간선을 비용순으로 정렬
edges.sort()

# 최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선
last = 0

# 비용이 작은 간선부터 하나씩 확인
for edge in edges:
    C, A, B = edge
    # 사이클이 발생하지 않는 경우(다른 집합인 경우) 집합에 포함하고 비용 증가
    if find_house(parent, A) != find_house(parent, B):
        union_house(parent, A, B)
        result += C
        last = C

print(result - last)

 

해설

임의의 두 집 사이에 경로가 항상 존재해야 한다

→ 크루스칼 알고리즘으로 최소 신장 트리를 찾는다.

마을을 2개의 분리된 마을로 분할할 계획을 세우고 있다.

→ 최소 신장 트리를 구성하는 간선 중에서 가장 비용이 큰 간선을 제거하면 최소 신장 트리가 2개의 그래프로 나누어지면서, 길의 유지비의 합을 최소로 할 수 있다.

 

---

 

입력받은 간선 데이터

edges = [(3, 1, 2), (2, 1, 3), (1, 3, 2), (2, 2, 5), (4, 3, 4), (6, 7, 3), (5, 5, 1), (2, 1, 6), (1, 6, 4), (3, 6, 5), (3, 4, 5), (4, 6, 7)]

 

비용순으로 정렬

edges = [(1, 3, 2), (1, 6, 4), (2, 1, 3), (2, 1, 6), (2, 2, 5), (3, 1, 2), (3, 4, 5), (3, 6, 5), (4, 3, 4), (4, 6, 7), (5, 5, 1), (6, 7, 3)]

 

현재 parent 테이블

parent = [0, 1, 2, 3, 4, 5, 6, 7]

 

비용이 작은 간선부터 하나씩 확인

 

(1, 3, 2)

find_house(parent, 3) = 3

find_house(parent, 2) = 2

루트 노드 값이 다르다 → 사이클이 발생하지 않았다 → 집합에 포함시킨다(간선으로 이어져있으니까)

union_house(3, 2) 수행 후 parent 테이블

parent = [0, 1, 2, 2, 4, 5, 6, 7]

집합에 포함시켰으므로 비용을 증가시킨다.

현재 집합에 포함된 집 : 2, 3

총 비용(result) : 1

 

(1, 6, 4)

find_house(parent, 6) = 6

find_house(parent, 4) = 4

루트 노드 값이 다르다 → 사이클이 발생하지 않았다 → 집합에 포함시킨다(간선으로 이어져있으니까)

union_house(6, 4) 수행 후 parent 테이블

parent = [0, 1, 2, 2, 4, 5, 4, 7]

집합에 포함시켰으므로 비용을 증가시킨다.

현재 집합에 포함된 집 : 2, 3 / 4, 6

총 비용(result) : 1 + 1 = 2

 

(2, 1, 3)

find_house(parent, 1) = 1

find_house(parent, 3) = 2

루트 노드 값이 다르다 → 사이클이 발생하지 않았다 → 집합에 포함시킨다(간선으로 이어져있으니까)

union_house(1, 3) 수행 후 parent 테이블

parent = [0, 1, 1, 2, 4, 5, 4, 7]

집합에 포함시켰으므로 비용을 증가시킨다.

현재 집합에 포함된 집 : 1, 2, 3 / 4, 6

총 비용(result) : 1 + 1 + 2 = 4

 

(2, 1, 6)

find_house(parent, 1) = 1

find_house(parent, 6) = 4

루트 노드 값이 다르다 → 사이클이 발생하지 않았다 → 집합에 포함시킨다(간선으로 이어져있으니까)

union_house(1, 6) 수행 후 parent 테이블

parent = [0, 1, 1, 2, 1, 5, 4, 7]

집합에 포함시켰으므로 비용을 증가시킨다.

현재 집합에 포함된 집 : 1, 2, 3, 4, 6

총 비용(result) : 1 + 1 + 2 + 2 = 6

 

(2, 2, 5)

find_house(parent, 2) = 1

find_house(parent, 5) = 5

루트 노드 값이 다르다 → 사이클이 발생하지 않았다 → 집합에 포함시킨다(간선으로 이어져있으니까)

union_house(2, 5) 수행 후 parent 테이블

parent = [0, 1, 1, 2, 1, 1, 4, 7]

집합에 포함시켰으므로 비용을 증가시킨다.

현재 집합에 포함된 집 : 1, 2, 3, 4, 5, 6

총 비용(result) : 1 + 1 + 2 + 2 + 2= 8

 

(3, 1, 2)

find_house(parent, 1) = 1

find_house(parent, 2) = 1

루트 노드 값이 같다 → 사이클이 발생하였다 → 이미 같은 집합

 

(3, 4, 5)

find_house(parent, 4) = 1

find_house(parent, 5) = 1

루트 노드 값이 같다 → 사이클이 발생하였다 → 이미 같은 집합

 

(3, 6, 5)

find_house(parent, 6) = find_house(parent, 4) = 1

find_house(parent, 5) = 1

루트 노드 값이 같다 → 사이클이 발생하였다 → 이미 같은 집합

parent = [0, 1, 1, 2, 1, 1, 1, 7]

 

(4, 3, 4)

find_house(parent, 3) = find_house(parent, 2) = 1

find_house(parent, 4) = 1

루트 노드 값이 같다 → 사이클이 발생하였다 → 이미 같은 집합

parent = [0, 1, 1, 1, 1, 1, 1, 7]

 

(4, 6, 7)

find_house(parent, 6) = 1

find_house(parent, 7) = 7

루트 노드 값이 다르다 → 사이클이 발생하지 않았다 → 집합에 포함시킨다(간선으로 이어져있으니까)

union_house(6, 7) 수행 후 parent 테이블

parent = [0, 1, 1, 1, 1, 1, 1, 1]

집합에 포함시켰으므로 비용을 증가시킨다.

현재 집합에 포함된 집 : 1, 2, 3, 4, 5, 6, 7

총 비용(result) : 1 + 1 + 2 + 2 + 2 + 4= 12

 

(5, 5, 1)

find_house(parent, 5) = 1

find_house(parent, 1) = 1

루트 노드 값이 같다 → 사이클이 발생하였다 → 이미 같은 집합

 

 

(6, 7, 3)

find_house(parent, 7) = 1

find_house(parent, 3) = 1

루트 노드 값이 같다 → 사이클이 발생하였다 → 이미 같은 집합

 

모든 간선 확인 완료

 

최소 신장 트리의 비용은 12인데 트리를 두 개로 나눠야 하므로(마을 2개) 최소 신장 트리 내의 가장 긴 간선인 4를 빼주면 답은 8이 나온다.

 

 

 

---

참고

2021.08.04 - [자료구조 알고리즘] - [알고리즘] 신장트리 / 크루스칼 알고리즘 : 최소 신장 트리 알고리즘

[알고리즘] 신장트리 / 크루스칼 알고리즘 : 최소 신장 트리 알고리즘

 

출처

나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년