문제
상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다.
하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.
이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자.
상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.
입력
첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고,
각 테스트 케이스마다 다음과 같은 정보가 주어진다.
첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 주어진다.
이후 M개의 줄에 a와 b 쌍들이 입력된다. a와 b를 왕복하는 비행기가 있다는 것을 의미한다. (1 ≤ a, b ≤ n; a ≠ b)
주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.
출력
테스트 케이스마다 한 줄을 출력한다.
상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다.
예제 입력
2
3 3
1 2
2 3
1 3
5 4
2 1
2 3
4 3
4 5
예제 출력
2
4
내가 했던 풀이 방법
최소 신장 트리 (Minimum Spanning Tree)의 간선 개수(nation-1)을 출력한다.
이에 대한 자세한 설명은 하단에 정리하였다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cases = Integer.parseInt(br.readLine());
String[] input;
int nation, airplane;
for(int i=0; i<cases; i++) {
input = br.readLine().split(" ");
nation = Integer.parseInt(input[0]);
airplane = Integer.parseInt(input[1]);
int[][] way = new int[airplane][2];
for(int j=0; j<airplane; j++) {
input = br.readLine().split(" ");
way[j][0] = Integer.parseInt(input[0]);
way[j][1] = Integer.parseInt(input[1]);
}
System.out.println(nation-1);
}
}
}
회고
문제를 읽자마자 최소 신장 트리를 이용해야하는 것을 알아버렸는데 (비행기를 타는 횟수가 아니라 종류를 물어봤기에), 이를 직접 구현하려니까 적당한 방법이 안 떠올라서 알고리즘을 찾아보려다가 정답을 발견한 문제... (입력때문에 코드가 길 뿐이지 실질적인 코드는 1줄이라는 점) 허무하기도 하고,,,허허허 차라리 간 순서를 출력하는거면 좋았을텐데 (그랬으면 티어가 높았으려나)
일단 최소 신장 트리 개념은 기억하고 있긴했지만, 구현자체는 못한 것이나 비슷하기에 최소 신장 트리에 대해 간단하게 정리하고 가겠다.
최소 신장 트리 (Minimum Spanning Tree)
다음과 같은 트리를 모두 신장 트리라고 하는데, 아래와 같은 특징을 가진다.
그래프의 모든 정점을 포함하는 트리
그래프의 최소 연결 부분 그래프로 사이클이 없음
정점의 개수 n개면 간선의 개수 n-1개 가짐 -> 이번 문제의 핵심
하나의 그래프에 많은 신장 트리 존재
DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다.
이 중 가중치 합이 가장 최소인 트리가 최소 신장 트리이다.
최소 신장 트리를 구현하는 알고리즘은 대표적으로 Prim과 Kruskal 알고리즘이 있다.
Kruskal 알고리즘
그래프의 간선을 하나씩 늘리며 MST를 만든다. 가중치가 최소인 간선부터 추가한다.
1) 간선은 가중치를 기준으로 오름차순 정렬한다.
2) 간선을 MST에 추가했을 때 MST에 사이클이 생기지 않으면 추가한다. 사이클이 생긴다면 다음 간선으로 넘어간다.
Prim 알고리즘
그래프의 정점 하나씩 늘리며 MST를 만든다. 정점과 연결된 간선의 가중치가 최소인 것부터 추가한다.
1) 시작 정점을 MST에 추가한다.
2) 간선과 이어진 다음 정점이 MST에 있지 않다면 이 정점과 간선을 최소 힙에 추가한다.
3) 최소 힙에서 꺼낸 정점이 MST에 포함되어 있지 않다면 MST에 추가하고 2)를 진행한다.
만약 꺼낸 정점이 MST에 포함되어 있으면 넘어간다.
4) 최소 힙이 빌 때까지 3)을 반복한다.
참고 자료
