Dev_Diary

https://www.acmicpc.net/problem/17472구현 + 최소 스패닝 트리 문제입니다. 구현 때문에 귀찮은 부분이 많을 뿐 사실 최소 스패닝 트리의 정석과 같은 문제입니다.해당 문제의 풀이는 크게 세 부분으로 나누어집니다. 1. 섬의 구분2. 섬 사이의 연결 탐색3. 최소 스패닝 트리 형성 1. 섬의 구분 같은 경우에는 DFS 나 BFS 혹은 Union-Find 등 그래프 탐색을 이용해 연결되어 있는 땅을 찾아주면 됩니다. 2. 섬 사이의 연결 탐색의 경우 섬의 모든 부분에서 네 방향으로 뻗어나가는 탐색 경로를 짜 가장 먼저 탐색되는 땅이 다른 섬인 경우 [현재 섬의 그룹, 다른 섬의 그룹, 거리] 의 형식으로 엣지를 형성해 기록해 줍니다. 3. 최소 스패닝 트리는 2 에서 만든 엣지를..

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/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: ..