최소스패닝트리

Algorithm/Baekjoon Online Judge
[Java] 백준 1774 (우주신과의 교감) Gold 4
Problem : https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net Approach MST(Minimum Spanning Tree) 를 응용한 문제이다. 이미 사용된 간선이 존재할 때, 나머지 간선들로 MST를 구성하면 된다. 나는 크루스칼 알고리즘을 사용하였다. 이미 사용된 간선들을 union으로 묶은 뒤, 간선의 길이가 작은 것부터 PQ에서 꺼내 연결하였다. 연결할 때마다 res 변수에 간선의 길이를 저장했고, 모두..
→2021.04.05
Algorithm/Baekjoon Online Judge
[Java] 백준 1197 (최소 스패닝 트리) Gold 4
Problem : 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 Approach MST(Minimum Spanning Tree) 를 구하는 데에는 크게 Prim과 Kruskal알고리즘이 있다. 이 문제는 간단하게 위 두 알고리즘 중 하나를 택하여 구현만 하면 되는 문제였다. 간단한 로직만 설명하고, 자세한 내용은 다루지 않겠다. Prim알고리즘은 간선 중심 알고리즘이다. 간선을 오름차순으로 정렬한..
→2021.03.30

• 이전
• 1
• 다음