Dev_Diary

https://www.acmicpc.net/problem/14950전형적인 최소 스패닝 트리 알고리즘입니다.추가 비용을 계속 갱신해주며 더해주면 됩니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, node): # 그룹의 대표가 자신이 아니면 if group_list[node] != node: # 재귀적으로 업데이트 group_list[node] = Find(group_list, group_list[node]) return group_list[node]# Uniondef Union(group_list, n1, n2): # 그룹 g1 = Find(group_l..

https://www.acmicpc.net/problem/10423최소 스패닝 트리 응용 문제입니다.노드끼리 연결할 때 각 노드에 순환이 생길 때 뿐만 아니라 각 노드의 그룹에 발전기가 속해있는지 체크해주고 두 그룹에 모두 발전기가 속해있다면 연결하지 않으면 됩니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, n): # 자신이 그룹의 대표가 아니면 if group_list[n] != n: # 재귀적으로 업데이트 group_list[n] = Find(group_list, group_list[n]) return group_list[n]# Uniondef Union(gro..

https://www.acmicpc.net/problem/14621최소 스패닝 트리 문제입니다.Union 을 진행하기 전에 엣지의 양끝에 있는 노드가 다른 성별을 이루고 있는지만 추가적으로 확인하면 풀 수 있습니다.import sysinput = sys.stdin.readline## Union-Find# Uniondef Union(group_list, node1, node2): # 그룹 g1 = Find(group_list, node1) g2 = Find(group_list, node2) # 같은 그룹이면 if g1 == g2: # 변합하지 않음 return False, group_list # 다른 그룹이면 작은 그룹으로 병합 if g1 > ..

https://www.acmicpc.net/problem/16398최소 스패닝 트리 문제입니다.두 행성을 잇는 간선을 정리해 크루스칼 알고리즘으로 풀었습니다. import sysinput = sys.stdin.readline# union-finddef Union(group_list, n1, n2): # 그룹 g1 = Find(group_list, n1) g2 = Find(group_list, n2) # 두 그룹이 같으면 if g1 == g2: # 병합하지 않음 return False, group_list # 다르면 그룹이 작은쪽으로 병합 if g1 > g2: group_list[g1] = g2 else: ..

https://www.acmicpc.net/problem/6497최소 스패닝 트리 문제입니다.크루스칼 알고리즘으로 풀었습니다.import sysinput = sys.stdin.readline## Union-Find# Uniondef Union(group_list, n1, n2): # 각 그룹 g1 = Find(group_list, n1) g2 = Find(group_list, n2) # 두 그룹이 같으면 if g1 == g2: # 병합하지 않음 return False, group_list # 두 그룹이 다르면 # 작은 쪽으로 병합 if g1 > g2: group_list[g1] = g2 else: ..

https://www.acmicpc.net/problem/1774최소 스패닝 트리 문제입니다.먼저 연결된 엣지들은 미리 같은 그룹으로 묶어놓은 뒤 크루스칼 알고리즘을 돌리면 풀 수 있습니다.import syssys.setrecursionlimit(1000)input = sys.stdin.readline## Union-Find# Uniondef Union(node1, node2, group_list): # 각 노드의 그룹 group1 = Find(node1, group_list) group2 = Find(node2, group_list) # 두 그룹이 같으면 if group1 == group2: # 병합하지 않음 return False, group_lis..

https://www.acmicpc.net/problem/2887최소 스패닝 트리의 응용 문제입니다.해당 문제의 가장 큰 문제는 최소 스패닝 트리를 찾는 알고리즘 자체보다는 어떤 엣지를 타겟으로 삼아야할지 정하는 것 입니다. N==100,000 이라고 한다면 모든 엣지를 탐색하기에는 시간이 부족하거나 메모리가 부족할 것이기 때문입니다.그렇다면 어떤 엣지가 최소 스패닝 트리를 구성하는 엣지가 될 수 있는지 생각해보아야 하는데, 단순히 생각해보면 가장 인접해있는 점이 그 후보에 가장 가깝다는 것을 알 수 있습니다. 가장 거리가 가까울테고, 가장 가까운 점은 하나일테니 어떤 두 점이 연결되었다면 다른 점에 연결될 가능성이 없어 순환이 발생하지도 않습니다.다만 해당 문제에서 엣지의 코스트는 두 점의 절대적인 거..

https://www.acmicpc.net/problem/1197최소 스패닝 트리의 기초 문제입니다.크루스칼 알고리즘으로 풀었습니다.다만 ReculsionError 가 발생할 수 있으니 sys.setrecursionlimit() 함수를 사용해 재귀 제한을 올려준 뒤 메모리 제한을 대비해 Pypy 대신 Python 으로 채점하면 되겠습니다.import syssys.setrecursionlimit(100000)input = sys.stdin.readline## Union-Find# Uniondef Union(node1, node2, group_list): # 각 노드의 그룹 group1 = Find(node1, group_list) group2 = Find(node2, group_list) ..

https://www.acmicpc.net/problem/1647최소 스패닝 트리 문제입니다.우선 모든 마을이 연결되게 하는 최소 코스트를 구한 뒤 가장 코스트가 큰 길을 지우면 코스트 합이 가장 작은 두 개의 마을이 됩니다.import sysinput = sys.stdin.readline# 크루스칼 알고리즘을 위한 Union-Find# Uniondef Union(root_list, node_1, node_2):    # 각 노드의 루트    root_1 = Find(root_list, node_1)    root_2 = Find(root_list, node_2)    # 각 루트가 같으면    if root_1 == root_2:        return False    # 다르면 루트가 작은쪽으로 병..

https://www.acmicpc.net/problem/1197말 그대로 최소 스패닝 트리 문제입니다.크루스칼 알고리즘을 통해 쉽게 풀 수 있습니다.다만 recursion error 가 발생할 때에는 연결된 엣지의 수가 N-1 을 초과하지 않았는지 체크해주면 됩니다. import sysinput = sys.stdin.readline# 크루스칼 알고리즘을 위한 Union-Find# Uniondef Union(root_list, node_1, node_2):    # 각 노드의 루트    root_1 = Find(root_list, node_1)    root_2 = Find(root_list, node_2)    # 각 루트가 같으면    if root_1 == root_2:        return F..