백준 상근이의 여행 (JAVA), 그림 설명과 함께

soluinoon·2023년 6월 10일

알고리즘 저지

목록 보기

11/13

문제

문제링크

풀이

최소 신장 트리의 기본 개념을 묻는 문제입니다.
최근 코딩 테스트에서도 나왔었던 문제라서 개념을 짚고 넘어가시는게 좋습니다.
필자는 이 개념을 몰라서 눈물을 머금고 틀릴 수 밖에 없었습니다...

접근 방법

n개의 노드를 모두 이을 수 있는 최소 간선의 갯수는 몇개일까?

그림으로 한번 유추해봅시다.

핵심 원리

💡 문제는 간선이 양방향이고, 실패할 경우는 주어지지 않는다는 점을 전제로 합니다

노드가 2개일 때 1개의 간선으로 모든 노드를 이을 수 있습니다.

노드가 3개일 때 2개의 간선으로 모든 노드를 이을 수 있습니다.

이 반복적인 작업에서 얻을 수 있는 답은 다음과 같습니다.

✅ n개의 노드를 모두 이을 수 있는 최소 간선의 갯수는 n-1개 이다.

이것을 기억하고 문제를 보면 왜 실버4 문제인지 알 수 있을 겁니다.

테스트 케이스 뜯어보기

문제의 2번째 테스트 케이스를 그림으로 보겠습니다.

저희가 가진 단서는 다음과 같습니다.

문제는 실패경우를 주지 않는다.
양방향이다.
n개의 노드를 모두 이을 수 있는 최소 간선의 갯수는 n-1개 이다.

따라서 답은 노드의 갯수인 5에서 1을 뺀 4입니다. 실패경우가 없고, 양방향이기 때문에 문제에서 요구하는 '최소의 비행기(간선)으로 모두 여행(모든 노드 방문)하기'는 법칙에 따라 n-1일 수 밖에 없기 때문입니다.

따라서 어떤 케이스가 와도 답은 노드에서 갯수를 1개 빼서 출력하면 됩니다.

전체 코드

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

public class Main {

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

        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int node = Integer.parseInt(st.nextToken());
            int airPlane = Integer.parseInt(st.nextToken());
            System.out.println(node - 1);
            for (int j = 0; j < airPlane; j++) {
                br.readLine();
            }
        }
    }
}