[정글 알고리즘] - [하] - 백준 9372 - 상근이의 여행- 실버 4

이 문제는 그래프를 직접 탐색해야 할 것처럼 보이지만, 실제 핵심은 훨씬 단순하다. 모든 국가를 여행할 수 있도록 하되, 비행기 종류 수를 최소로 만들어야 한다는 점만 정확히 이해하면 정답은 바로 나온다. [Source]

문제 요약

상근이는 N개의 국가를 여행하려고 하고, 주어진 비행 스케줄 안에서 가능한 한 적은 종류의 비행기를 타고 모든 국가를 방문하고 싶다. 한 국가에서 다른 국가로 갈 때 중간에 다른 국가를 거쳐 가도 된다. 

항목	내용
입력	테스트케이스 수 T, 각 테스트케이스마다 국가 수 N, 비행기 종류 수 M, 그리고 M개의 간선 정보
출력	모든 국가를 방문하기 위한 최소 비행기 종류 수
핵심 해석	모든 국가를 연결하기만 하면 되고, 최소 간선 수를 묻는 문제

처음 보면 이렇게 접근하기 쉽다

문제를 처음 읽으면 보통 그래프를 그리고, DFS나 BFS로 연결 여부를 확인해야 할 것처럼 느껴진다. 실제로 나라도 정점, 비행기 노선도 간선이므로 그래프로 표현하는 발상 자체는 맞다.

간선 리스트

edges = [(1, 2), (2, 3), (3, 4)]

인접 리스트

1: [2]
2: [1, 3]
3: [2, 4]
4: [3]

하지만 이 문제는 그래프를 실제로 탐색하지 않아도 된다. 핵심은 “최소한의 간선만으로 모든 나라를 연결하는 수”가 얼마인지 아는 것이다.

진짜 핵심: 정답은 항상 N-1

모든 국가를 연결해서 방문 가능하게 만들면서, 비행기 종류 수를 최소로 하려면 사이클이 없어야 한다. 즉, 최소 연결 구조는 결국 트리와 같다.

트리는 정점이 N개일 때 간선이 정확히 N-1개다. 따라서 이 문제의 정답도 항상 N-1이 된다.

왜 그런가?

국가가 1개면 비행기 0개

국가가 2개면 최소 1개

국가가 3개면 최소 2개

국가가 4개면 최소 3개

즉, 새로운 국가 하나를 연결할 때마다 최소 비행기 종류 1개가 더 필요하므로 항상 N-1이다.

예제 1을 그림으로 이해하기

예를 들어 나라가 4개 있고, 다음처럼 연결되어 있다고 하자.

1 - 2 - 3 - 4

이 경우 나라 4개를 모두 연결하는 데 필요한 최소 비행기 종류 수는 3개다. 이미 선 하나가 나라 둘을 연결하고 있으므로, 4개를 모두 하나의 연결된 구조로 만들기 위해서는 최소 3개의 간선이 필요하다.

국가 수	최소 비행기 종류 수
1	0
2	1
3	2
4	3

그럼 왜 비행기 정보 M개를 입력받나?

여기서 많이 헷갈리는 부분이 바로 이것이다. 정답이 어차피 N-1이면, 뒤에 주어지는 M개의 간선 정보는 왜 읽어야 할까?

정답 계산용은 아니다

하지만 입력 형식상 간선 정보를 끝까지 읽어야 다음 테스트케이스로 정상적으로 넘어갈 수 있다.

즉, 간선은 계산에 직접 쓰지 않아도 입력 소비를 위해 반드시 읽어야 한다는 점이 중요하다.

구현 흐름은 정말 짧다

1단계

테스트케이스 수 T 입력

2단계

각 테스트케이스마다 N, M 입력

3단계

M개의 간선 입력을 그냥 읽기

4단계

N-1 출력

헷갈리기 쉬운 포인트

실수 포인트	왜 문제인가	정리
TreeNode 같은 구조를 만들려는 경우	이 문제는 트리를 구성하거나 탐색하는 문제가 아님	정답은 N-1만 알면 됨
DFS/BFS를 꼭 돌려야 한다고 생각하는 경우	연결 그래프라는 전제에서 최소 간선 수는 이미 결정됨	탐색 없이 해결 가능
간선 입력을 아예 안 읽는 경우	다음 테스트케이스 입력이 꼬임	반드시 M줄 입력 소비

제출용 정답 코드

t = int(input())

for _ in range(t):
    n, m = map(int, input().split())

    for _ in range(m):
        a, b = map(int, input().split())

    print(n - 1)

공부용으로는 결과를 모아서 출력해도 좋다

온라인 저지에서는 각 테스트케이스마다 바로 출력해도 되고, 마지막에 한 번에 출력해도 된다. 로컬에서 공부할 때는 결과를 리스트에 모아 두었다가 마지막에 출력하는 방식이 흐름을 보기 더 편할 때가 많다.

공부용 버전

t = int(input())
results = []

for _ in range(t):
    n, m = map(int, input().split())

    for _ in range(m):
        a, b = map(int, input().split())

    results.append(n - 1)

for r in results:
    print(r)

왜 이 코드가 맞는가?

모든 나라를 방문 가능하게 만들려면 결국 전체 국가를 하나의 연결된 구조로 만들어야 한다.

그 연결 구조에서 간선 수를 최소로 하려면 사이클이 없어야 하고, 그런 최소 연결 구조가 바로 트리다.

트리의 간선 수 = 정점 수 - 1 = N - 1

마무리

이 문제는 그래프 문제처럼 생겼지만, 실제로는 트리의 가장 기본 성질 하나로 끝나는 문제다.

처음엔 간선을 저장하고 DFS/BFS를 떠올리기 쉽지만, 문제를 한 번 더 단순화해 보면 “모든 국가를 연결하는 최소 간선 수”만 묻고 있다는 걸 알 수 있다.

그래서 이 문제의 핵심 한 줄은 이것이다. 정답은 항상 N-1, 간선 입력은 읽기만 하면 된다.