BOJ_9372 : 상근이의 여행

👉 문제링크

9372번: 상근이의 여행

---

---

🔸 문제 분석 🔸

• T개의 테스트 케이스마다 결과를 출력한다.
  • 국가의 수 n과 비행기의 종류 m을 입력 받는다.
  • m개의 비행기 종류 마다 a, b 쌍을 입력 받는다.
  • 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.
  • 모든 국가를 여행할 때 가장 적은 종류의 비행기로 탄다면 몇 개의 종류인지 출력한다. 

[연결 그래프]
그래프 이론에서 연결 그래프(connected graph)는 모든 두 꼭짓점 사이에 경로가 존재하는 그래프이다.

• 따라서 모든 국가(노드)로 가는 경로가 존재하므로, 최소 비행기 종류 수는 시작 위치를 제외한 나머지 국가(노드)의 수 이다. (== n - 1)

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            for (int i = 0; i < m; i++) {
                sc.nextInt();
                sc.nextInt();
            }

            System.out.println(n-1);
        }
    }
}

🔸 코드 해석 🔸

• 문제 형식의 모든 입력을 받을 수 있도록 한다.
• n-1을 출력한다.

---

🔸 end 🔸

• 문제를 보자마자 연결 그래프의 뜻을 검색했는데, 모든 노드가 연결되어 있는건지 아닌지 헷깔렸다.
  • 하지만 문제 자체에 모든 국가를 여행 할 때의 비행기 종류 수라고 했으므로, 바로 n-1을 제출해 보았는데 바로 통과되었다.
• 문제 질문을 보니, 사람들이 통과해도 이게 맞는건지 되묻는 질문이 많았다.
  • 출제의도는 n-1을 출력하는게 맞다고 한다.