[python][백준] 1647번 도시분할계획

🚀  들어가며...

• 크루스칼 알고리즘과 유니온파인드를 이용하는 문제입니다.
• 난이도는 골드4 레벨 문제입니다.

 

🔗 문제  

https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

 

📑 내용

[ 문제 설명 ]

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.

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

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

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

[ 제한 조건 ]

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

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

[ 입출력 예 ]

🔗 풀이

1. 입력 받은 간선을 비용을 기준으로 내림차순 정렬 합니다.

2. 비용이 낮은 간선부터 사이클 여부를 확인하고 사이클이 발생하지 않으면 삽입합니다.

3. 모든 간선에 대해서 위 과정을 수행한 후 제일 마지막에 삽입한 간선을 제거합니다.

 

💌 소스코드

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


def union_parent(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


n, m = map(int, input().split())  # 집의 개수, 길의 개수 입력받기
graph = []
for _ in range(m):  # 길 입력받기
    a, b, c = map(int, input().split())
    graph.append([c, a, b])

parent = [0] * (n + 1)
for i in range(1, n + 1):
    parent[i] = i

# 간선 정렬
graph.sort()

# 크루스칼 수행
selected = []  # 선택된 간선

answer = 0
for c, a, b in graph:
    if find_parent(a) != find_parent(b):
        union_parent(a, b)
        answer += c
        selected.append(c)

# 마을을 두개로 분리하기 위해서 마지막 간선 제거
answer -= selected.pop()

# 출력
print(answer)

 

🙋🏻‍♂️ 후기

이번 문제는 우선 유니온파인드가 핵심이며, 크루스칼 알고리즘도 선수지식이 필요한 문제여서 난이도가 굉장히 높았습니다. 저도 처음에는 문제가 잘 풀리지 않아 필요한 개념을 공부하면서 풀어보았습니다. 유니온파인드는 한번 이해하고 코드를 구현할 줄 알면, 비슷한 문제에서도 응용이나 그대로 사용하기가 가능하기 때문에 꼭 이해해보시는 것을 추천드립니다. (이전글 참고)