[BaekJoon] 9372번 상근이의 여행 (Java) 문제 풀이 [Silver 4]

문제

https://www.acmicpc.net/problem/9372

9372번: 상근이의 여행

 

어떻게 풀 것인가?

다소 깊게 생각하면 어렵지만, 수학적으로 접근하면 너무너무 쉬운 문제였다.

가장 적은 종류의 비행기를 타고 모든 국가들을 여행 <- 이 문장에 얽메이면 최소경로?, 최소신장트리? 라고 생각할 수 있지만,

트리로 생각해보자.

 

트리의 노드가 N라고 가정했을 때, 최소 간선의 갯수는 N-1개이다. 이것이 정답이다...

 

풀면서 놓쳤던점

어렵게 생각하지 말자.

이 문제를 통해 얻어갈 것

트리에 대한 기본적인 이해

내 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;


// 백준알고리즘 9372번 상근이의 여행

public class Main {
    static int T;
    static int N, M;

    static LinkedList<Integer>[] list;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        for (int test_case = 0; test_case < T; test_case++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());

            list = new LinkedList[N + 1];

            for (int i = 0; i <= N; i++) {
                list[i] = new LinkedList<>();
            }

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                list[a].add(b);
                list[b].add(a);

            }

            sb.append(N - 1).append("\n");

        }
        System.out.println(sb);

    }
}

참고

X