💯Problem Solving
[BOJ] 1647 도시분할계획
date
Aug 5, 2023
slug
boj-1647
author
status
Public
tags
Python
BOJ
summary
백준 1647번 문제풀이입니다.
type
Post
thumbnail
category
💯Problem Solving
updatedAt
Aug 20, 2023 11:14 AM
문제 링크
문제
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.
마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.
문제풀이
크루스칼 알고리즘을 사용해서 MST를 구하고 거기서 가장 큰 간선, 즉 마지막 간선을 제거해주면
마을이 두개로 분할되면서 문제의 조건을 모두 만족한다.
이 문제의 핵심은 결국 크루스칼 알고리즘 이므로,
크루스칼알고리즘을 다시 요약하자면
- 간선을 가중치 순으로 오름차순한다.
- 모든 간선을 돌면서 사이클에 포함되지 않는 간선인 경우 Find(a) ≠ Find(b) Union연산을 진행하여, a와 b의 최종 부모를 일치시키는 작업. 같은 disjoint-set으로 만들고 MST에 포함시킨다.
- 사이클에 포함되는 경우 건너뛴다.
- 이렇게 모든 간선에대해 진행하거나, count를 사용하여 정점의 갯수 -1이 될때 종료하게 끔하면 된다.
파이썬 문제풀이 코드
import sys input = sys.stdin.readline N, M = map(int, input().split()) graph = [] ancestor = [i for i in range(N+1)] for _ in range(M): A, B, C = map(int, input().split()) graph.append((A, B, C)) graph.sort(key = lambda x:x[2]) # value기준 오름차순 정렬 # Union def union(a, b): pa = find(a) # a의 부모 찾기 pb = find(b) # b의 부모 찾기 ancestor[pb] = pa # b의 부모를 pa로 연결 # Find def find(node): # node의 부모 찾기 if node == ancestor[node]: # 만약 node가 부모의 노드와 같다며 return node # node의 부모는 node 자기자신 ancestor[node] = find(ancestor[node]) # 자기 자신 노드가 아니라면 부모의 노드로 다시 설정 return ancestor[node] # 압축한 경로 count = 0 weighted = [] for item in graph: #mst 생성과정 if count == len(ancestor)-1: # mst 완성 break A, B, C = item if A > B: # 작은 정점이 앞으로 A, B = B, A if find(A) != find(B): # not cycle union(A, B) # 같은 집합으로 두고 weighted.append(C) # mst에 포함 count += 1 print(sum(weighted[:-1]))
시간복잡도
입력
첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C (1 ≤ C ≤ 1,000)라는 뜻이다.
임의의 두 집 사이에 경로가 항상 존재하는 입력만 주어진다.
출력
첫째 줄에 없애고 남은 길 유지비의 합의 최솟값을 출력한다.