ALGORITHM/BOJ

[백준] 9372 상근이의 여행

0298 2020. 12. 5. 22:40

www.acmicpc.net/problem/9372

 

9372번: 상근이의 여행

첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가

www.acmicpc.net

2020-12-05


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.Scanner;
 
public class Main9372 {
    public static int N, M;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
        for(int ts = 1; ts <= test; ts++) {
            N = sc.nextInt();
            M = sc.nextInt();
            for(int i = 0; i < M; i++) {
                int a = sc.nextInt()-1;
                int b = sc.nextInt()-1;
            }
            System.out.println(N-1);
        }
    }
}
 
cs

 

문제를 풀기전에 분류를 기준으로 문제를 골라서 풀었다. 분류상 그래프 이론, 트리로 되어있었고, 문제를 처음 읽었을 때 MST로 풀어야햐는건가 아리까리 했었다.

 

그런데 문제가

"모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다."

라고 되어있다. 이 말 뜻은 결국 모든 국가(N)를 여행하면서 탈 수 있는 비행기의 최소 개수는 무조건 N-1이 된다라는 뜻이다.