[백준] 9372 상근이의 여행 - Java

문제 - 상근이의 여행

https://www.acmicpc.net/problem/9372

 

 

입력

첫 번째 줄에는 테스트 케이스의 수 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

---

접근방법

 

- 이 문제는 문제 안에 정답이 있다 

- 비행기를 타는 최소 횟수나 최단 거리 였다면 노드 만들고 그에 대한 간선을 만들고 해야 겠지만 

- 비행기의 종류를 구하라는 문제이다 -> 즉, N - 1이 정답이다

- 노드끼리 모두 연결되게 하기 위해서 필요한 최소 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 {

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int T = Integer.parseInt(st.nextToken());

            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 m = 0; m < M; m++) {
                    st = new StringTokenizer(br.readLine());
                }
                System.out.println(N - 1);
            }

        }
    }
}

---

풀고 느낀점

 

- 이 문제는 노드와 간선의 관계를 알고 있는지 그 개념에 대한 문제인 것 같다