-
[백준] 9372 상근이의 여행ALGORITHM/BOJ 2020. 12. 5. 22:40
2020-12-05
1234567891011121314151617181920import 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이 된다라는 뜻이다.
'ALGORITHM > BOJ' 카테고리의 다른 글
[백준] 11437, 11438 LCA (2) (0) 2020.12.07 [백준] 1946 신입사원 (0) 2020.12.06 [백준] 9466 텀 프로젝트 (0) 2020.12.01 [백준] 1747 소수&팰린드롬 (0) 2020.11.27 [백준] 1966 프린터 큐 (0) 2020.11.24