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

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

 

문제를 대충 읽고 가장 적은 종류 -> BFS! 하고 BFS 돌렸다가 깨달은 문제이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main  {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int a = Integer.parseInt(s);
        for (int i = 0; i < a; i++) {
            s = br.readLine();
            int[] arr = Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 0; j < arr[1]; j++) {
                br.readLine();
            }
            System.out.println(arr[0]-1);
        }
    }
}

주어지는 비행 스케줄은 항상 연결 그래프를 이룬다 -> 최소 신장 트리 -> 정점의 개수 -1개로 모든 노드를 순회할 수 있음