Dev_Diary

https://www.acmicpc.net/problem/1414문제자체는 단순한 최소 스패닝 트리 문제입니다.다만 입력을 숫자로 치환하는 과정이 추가된 문제입니다.import sysinput = 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_list # 두 그룹이 다르면 # 작은 쪽으로 병합 if..

https://www.acmicpc.net/problem/32339최소 스패닝트리 문제입니다.엣지를 정렬할 때 도로 선호도에 따라 추가적으로 정렬을 해준 뒤 추가적인 카운트만 해주면 풀 수 있습니다. 다만 제출시에 reculson error 가 발생하니 sys.setrecursionlimit 을 이용해 적절한 수치로 제한을 조정해주어야 합니다.import syssys.setrecursionlimit(10000)input = sys.stdin.readline# union-finddef Union(group_list, n1, n2): # 그룹 g1 = Find(group_list, n1) g2 = Find(group_list, n2) # 두 그룹이 같으면 if g1 == g2: ..

https://www.acmicpc.net/problem/2350최소 스패닝 트리 문제입니다.일반적인 최소 스패닝 트리가 아닌 최대 스패닝 트리를 만들어 타겟 노드 사이를 연결하는 노드 중 코스트가 최소인 엣지를 탐색해주면 됩니다.import sysfrom collections import dequeinput = 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 # 다르면 그룹..

https://www.acmicpc.net/problem/20010최소 스패닝 트리 문제입니다.최소 스패닝 트리는 크루스칼 알고리즘을 통해 구해주면 됩니다.그리고 그 중 가장 긴 경로를 구하는 경우는https://www.acmicpc.net/problem/1167해당 문제와 같은 경우입니다. 풀이는더보기임의의 노드를 골라 가장 먼 노드를 구한 뒤 해당 노드에서 다시 가장 먼 노드를 구하면 이는 가장 긴 경로가 된다는 내용입니다. 임의의 노드에서 가장 먼 노드를 고르면 트리의 가장 먼 두 노드 중 하나의 노드를 고르게 되므로 이를 두 번 진행하면 쉽게 구할 수 있습니다.import sysfrom collections import deque as dqinput = sys.stdin.readline## Uni..

https://www.acmicpc.net/problem/9344최소 스패닝 트리 문제입니다.다만 최소 스패닝 트리를 완성할 필요는 없고 트리를 만드는 과정 중 p, q 가 병합되었는지만 판단하면 됩니다. 크루스칼 알고리즘은 그리디 알고리즘이기 때문에 연결된 노드가 중간에 다시 끊어지는 경우가 없으므로 연결되는 순간 바로 출력해주어도 무관합니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, node): # 자신이 그룹의 대표가 아니면 if group_list[node] != node: # 재귀적으로 재탐색 group_list[node] = Find(group_list, group_..

https://www.acmicpc.net/problem/13905최소 스패닝 트리 문제..인데 그보다는 크루스칼 알고리즘 문제라고 하겠습니다.최소 스패닝 트리가 아닌 최대 스패닝 트리를 구하는 과정이 포함되기 때문입니다. 크루스칼 알고리즘을 통해 최대 스패닝 트리를 구하며 s 노드와 e 노드가 연결되는 순간 병합을 중단하고 s 노드에서 e 노드로 운반할 수 있는 최대 코스트를 그래프 탐색을 통해 구해주면 됩니다.import sysfrom collections import dequeinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, node): # 루트 노드가 아니면 if group_list[node] != node: ..

https://www.acmicpc.net/problem/1368최소 스패닝 트리 문제입니다. 그냥 크루스칼 알고리즘을 돌리면 되는데, 우물을 파는 비용을 고려해주어야 하기 때문에 한 가지 수정이 필요합니다. 인덱스가 N+1 인 가상의 노드를 생성한 뒤 이 노드는 '우물을 파는 가격' 에 대한 노드로 설정해줍니다. 즉 크루스칼 알고리즘을 이 N+1 노드를 포함해서 돌리게 되면 다른 노드와 연결하는 비용과 우물을 파는 비용들을 모두 합쳐 비교해 최소 비용을 계산할 수 있습니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, node): # 루트 노드가 아니면 if group_list[node] != node:..

https://www.acmicpc.net/problem/13418최소 스패닝 트리 문제입니다.다만 그닥 추천드리고 싶지 않은 문제입니다. 문제 자체는 그냥 크루스칼 알고리즘을 두 번 사용해 풀면 되기에 어렵지는 않지만 입력과 조건이 이상하다고 생각됩니다.분명 도로의 개수 M 이라고 작성되어 있지만 당장 입력에는 M+1 개의 도로가 주어집니다.다 풀어놓고도 입력 오류를 이유로 틀린 사람이 많을 것 같습니다. 코스트와 피로도가 반전되어 있다는 점과 입력이 이상하다는 점만 유의하면 쉽게 풀 수 있습니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, node): # 루트 노드가 아니면 if group_list[..

https://www.acmicpc.net/problem/21924최소 스패닝 트리 문제입니다.최소 스패닝 트리의 특성상 노드 개수가 N-1 이 아니면 모든 노드가 연결되지 않았다는 것만 알면 간단하게 풀 수 있습니다.import sysinput = sys.stdin.readline# Union-Finddef Union(root_list, node_1, node_2): # 각 노드의 루트 root_node_1 = Find(root_list, node_1) root_node_2 = Find(root_list, node_2) # 두 노드의 루트가 같으면 if root_node_1 == root_node_2: # 병합하지 않고 루트 리스트 리턴 return ..

https://www.acmicpc.net/problem/1185최소 스패닝 트리 응용 문제입니다.크루스칼 알고리즘을 위해 엣지를 정렬할 때 기준이 되는 비용을 재설정 해주어야 합니다. 기존 알고리즘에서는 엣지의 비용만을 생각하지만 해당 문제에서 다음 노드로 갈 때 고려해야 할 비용은A -> B 엣지의 비용 + B 노드 방문비용 + B -> A 엣지의 비용 + A 노드 방문비용이기 때문에 이를 기준으로 정렬해 알고리즘을 돌리면 해결할 수 있습니다.import sysinput = sys.stdin.readline# Union-Finddef Union(root_list, node_1, node_2): # 각 노드의 루트 root_node_1 = Find(root_list, node_1) ro..