ALGORITHM/BOJ
[백준] 9372 상근이의 여행
0298
2020. 12. 5. 22:40
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이 된다라는 뜻이다.