[MST] 백준 9372 상근이의 여행

Halo·2025년 6월 9일

Algorithm

목록 보기

57/85

🔍 Problem

백준 9372 상근이의 여행

📃 Input&Output

🌁 문제 배경

가. 문제 설명
각 이동지간에 왕복가능한 경로가 정해져있고 모든 경로가 연결되어있다는 가정하에 이용할 수 있는 비행기의 최소 개수를 구하는 문제이다.

나. 접근 방법
모든 연결되어있는 그래프의 최소 간선 개수를 생각해본다.

다. 사용할 알고리즘 선택
없음

📒 해결 과정

가. 비행기의 종류 수를 구하는 법
결국 비행기 한 종류는 하나의 간선을 의미한다. 한 나라에서 다른 나라로 갈 때, 하나의 간선을 이용하고 이것은 즉 비행기 한 종류를 의미하기 때문이다.

필자가 생각하기엔 문제 가독성이 좀 별로다.

💻 Code

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

public class P9372 {


    public static void main(String args[]) throws IOException {
        Scanner sc = new Scanner(System.in);

        int T;
        int node_cnt, edge_cnt;
        int tmp;

        T = sc.nextInt();

        for (int i = 0; i < T; i++) {
            node_cnt = sc.nextInt();
            edge_cnt = sc.nextInt();
            for (int j = 0; j < edge_cnt; j++) {
                tmp = sc.nextInt();
                tmp = sc.nextInt();
            }
            System.out.println(node_cnt - 1);
        }

    }
}