[백준] 단계별로 풀어보기(단계:31, 최소 신장 트리,JAVA)9372번, 상근이의 여행

문제 링크

9372번: 상근이의 여행

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

최소 신장 트리

신장 트리 : 어떤 그래프에 대하여 모든 꼭짓점을 포함하는부분 그래프입니다.

 

최소 신장 트리 : 신장 트리에서 최소의 가중치를 가지는 부분 그래프입니다. 

Minimum spanning tree - Wikipedia

이 문제에 핵심은

1. 입력되는 값이 그래프의 값입니다.

2. 탑승한 비행기의 종류를 출력하는 것으로 모든 선분의 가중치는 1입니다.

3. 모든 국가를 여행할 때 탑승하는 최소 비행기의 종류를 결과로 출력합니다.

 

해당 문제에 입력되는 그래프의 값들의 가중치는 항상 1입니다.

 

왜냐하면 결과에서 탑승하는 종류의 비행기 횟수를 다루고 있기 때문입니다.

 

입력되는 그래프에 대한 신장 트리는 모두 최소 신장 트리가 됩니다.

 

왕복을 진행한다고 해도 같은 비행기를 탑승한 것이기 때문에 가중치는 증가하지 않습니다.

 

결과적으로 다른 종류의 비행기를 탑승하는 개수는

 

개수 : 국가의 수 - 1

 

입력값에서 N이 국가의 수이기 때문에 각 테스트 케이스에 결과로 N-1을 출력하면 됩니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 사용하여 그래프에 대한 정보를 저장합니다.
• BufferedWriter에 각 테스트 케이스에 국가의 수 - 1의 값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

결과 코드

import java.io.*;
import java.util.*;

public class Main {
	static int T;
	static ArrayList<ArrayList<Integer>> graph;	//입력되는 그래프 저장 배열
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	//입력값 처리하는 BufferedReader
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        	//결과값 출력하는 BufferedWriter
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
        	//각 테스트 케이스 진행
		for(int i=0;i<T;i++) {
        	graph = new ArrayList<>();
			st = new StringTokenizer(br.readLine()," ");
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
            		//그래프 값 초기화
			for(int j=0;j<=N;j++) 
				graph.add(new ArrayList<>());
            		//그래프 값 저장
			for(int j=0;j<M;j++) {
				st = new StringTokenizer(br.readLine()," ");
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				graph.get(a).add(b);
				graph.get(b).add(a);
			}
			bw.write((N-1) + "\n");	// 국가의 수 - 1 값을 BufferedWriter 저장
		}
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
}