ATM

2023.09.17 (SUN)

---

문제 : 백준 - 9372. 상근이의 여행

---

조건 및 설명

접근법

1. 인접리스트로 그래프를 구현하고
2. 신장 트리로 최소 비용을 구한다.

1. 사실 이 문제는, 입력된 그래프가 항상 연결 그래프이므로 국가 - 1가 정답이다.

결과 코드

/*
 * Title : 상근이의 여행
 * Link : https://www.acmicpc.net/problem/9372
 */
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        // input
        int tc = Integer.parseInt(br.readLine());
        
        // each TestCase
        for (int t = 0; t < tc; t++) {
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken()); // number of countries
            int M = Integer.parseInt(st.nextToken()); // number of planes

            for (int i = 0; i < M; i++) { 
                br.readLine(); // we don't need to process the plane information for this problem.
            }
            
            System.out.println(N-1); // the minimum number of planes Sanggeun needs to take is always N-1.
        }
    }
}