하루살이 개발자

도시 분할계획 문제입니다. 문제링크: https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 풀이 최소 신장 트리 문제로 크루스칼 알고리즘, Union+find 이용하면 된다. 마지막에 두 마을로 쪼개야 하므로, 최소 신장 트리 결과에서 가장 큰 비용을 갖는 간선 하나를 제거하는 것이 포인트! Code # 최소신장트리 문제 # 크루스칼 알고리즘 import sys input = sys.stdin.readline #..

네트워크 연결 문제입니다. 문제링크:https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이 크루스칼 알고리즘, Union+find 알고리즘 이용하는 문제 Code # 최소신장트리 문제 # 크루스칼 알고리즘 import sys input = sys.stdin.readline # find 연산 def find_parent(parent, x): if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] # union 연산 def union_parent(pare..