백준 9372: 상근이의 여행(java)

문제

---

풀이

 

신창 트리를 이용하면 간단히 풀이할 수 있다.

 

신장 트리(spanning tree)란 그래프 내의 모든 정점을 포함하는 트리로, 모든 정점들이 연결되어 있어야 하고 사이클을 포함하지 않는다. 그래프에 n개의 정점이 있을 때, 이들을 (n-1)개의 간선으로 연결하는 것이다.

 

신장 트리는 그래프의 최소 연결 부분 그래프가 되는데, 이때 '최소'는 간선의 수가 가장 적음을 의미한다. n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 신장 트리이다. 

 

상근이는 국가를 방문하고자 하므로, 각 국가를 정점으로 생각한다면 M이나 a, b 쌍을 고려할 필요 없이 (N-1)을 출력함으로써 풀 수 있는 문제이다.

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int T=Integer.parseInt(br.readLine());
		for(int i=0; i<T; i++) {
			st=new StringTokenizer(br.readLine());
			int N=Integer.parseInt(st.nextToken());
			int M=Integer.parseInt(st.nextToken());
			
			for(int j=0; j<M; j++) {
				br.readLine();
			}//a, b는 입력만
			
			System.out.println(N-1);
		}
	}
}