[Tree-MST] 백준 : 9372_상근이의 여행

[inseonyun]

Source URL : 백준 : 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)
• 주어지는 비행 스케줄은 항상 연결 그래프를 이룬다.
• 테스트 케이스마다 한 줄을 출력한다.
• 상근이가 모든 국가를 여행하기 위해 타야 하는 비행기 종류의 최소 개수를 출력한다.

접근 방법 :

• 입력받은 연결 그래프 정보 a, b를 벡터에 넣고 해당 벡터를 탐색하며, 비용을 계산하도록 풀이하였다.
• 위 방법으로 오답처리를 받고 자세히 보니, 결국엔 N - 1만큼이 최소 값이 되게 된다....

풀이 순서 :

1. test_case를 입력받아 해당 test_case 크기만큼 반복하며 진행한다.
2. N과 M을 입력받아 M만큼 반복하여 a와 b를 입력 받는다.
3. N -1을 출력하며 test_case 반복

[inseonyun]

문제 풀이 결과 :