[ 백준 - 9372 ]상준이의 여행

문제를 보면 모든 노드들은 연결이 되어있고, 모든 노드들을 돌아볼 때 가장 적은 종류의 비행기( 간선 정보 )를 타고 움직이는 수를 알아내야하는 것이 문제의 의도 입니다.

 

이때 우리는 모든 노드가 연결되어있고, 최소한의 경로로 모든 노드를 방문해야한다는 조건에서 최소신장 트리를 떠올릴 수 있어야 합니다.

 

최소신장 트리의 모든 노드를 연결하면서 가중치의 합을 구하면 되겠는데, 이때 값은 N - 1로써 가장 간단하게 구할 수 있습니다.

(N은 노드 수입니다.)

 

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            for (int i = 0; i < m; i++) {
                br.readLine();
            }
            sb.append(n - 1).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        br.close();
        bw.close();
    }

}

• 시간복잡도: O(1)
• 공간복잡도: O(1)