프로그래밍 공부 노트

최소 스패닝 트리는 그래프를 이루는 에지 중 일부를 제거하여 트리 모양으로 만드는 것을 의미한다. 최소 스패닝 트리를 만드는 방법은 두 가지가 있는데, 하나는 크루스칼 알고리즘이고 다른 하나는 프림 알고리즘이다. 크루스칼 알고리즘은 모든 에지를 가중치 순으로 정렬한 뒤, 가중치가 작은 에지부터 그래프에 추가해 트리를 만드는 방식이다. 이 때 트리를 추가하는 기준이 오로지 에지의 가중치뿐이므로 잘못하면 사이클을 만들 수 있다. 사이클 방지를 위해선 각 노드의 부모 노드를 저장해야 하는데, 에지를 하나 추가할 때마다 에지에 연결된 두 노드에 대해 조상 노드, 즉 각 노드가 속한 트리의 루트 노드를 계산해야 한다. 만일 두 노드의 조상 노드가 같다면 에지를 추가했을 때 두 노드를 이동하는 경로가 둘 이상 생기..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 이 문제의 입력은 비용이 같은 에지를 노드에 상관없이 한 줄씩 입력하는 형태인데, 이는 최소 스패닝 트리를 만드는 크루스칼 기법과 유사하므로 크루스칼 기법을 이용하면 이 문제를 해결할 수 있다. #include using namespace std; #define MAX_N 500000 // parent[i]: 노드 i의 부모 노드 int parent[MAX_N + 1]; void swap(i..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 각 별을 노드, 별자리 위의 선을 에지, 별과 별 사이의 거리를 가중치로 두면, 이 문제는 최소 스패닝 트리를 구하는 문제이다. - 크루스칼 기법 #include #include #include using namespace std; typedef pair point; typedef pair edge; #define MAX_N 100 #define _y first #define _x second #d..

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 입력받은 그래프를 두 개의 트리로 만드는 문제이다. 이 때 만들어진 두 트리의 가중치의 합을 최소화해야 하므로, 이 문제는 최소 스패닝 트리 문제라고 할 수 있다. - 크루스칼 기법 크루스칼 기법을 사용하면서 트리의 개수를 추적하다가, 트리의 개수가 2개 이하로 내려가는 순간 기법을 멈추고 가중치의 총합을 출력한다. 후술할 프림 알고리즘과 마찬가지로 트리를 완..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리를 만드는 알고리즘은 크루스칼(Kruskal) 기법과 프림(Prim) 기법이 있는데, 두 방법 모두 이용해서 풀어보도록 하자. - 크루스칼 기법 크루스칼 기법은 모든 에지를 가중치가 작은 순으로 트리에 추가하고, 사이클이 생기는 에지는 버리며 모든 노드에 방문했을 때 트리 생성을 종료하는 알고리즘이다. 이 때 크루스칼 기법은 각 노드를..