[정글 알고리즘] - [하] - 백준 14244- 트리 만들기 실버4

이 문제는 복잡한 트리 알고리즘을 묻는 문제가 아니라, 리프 노드 개수를 정확히 맞추는 트리 구조를 직접 구성하는 문제다. 핵심은 “어떤 모양으로 연결하면 리프가 몇 개 생기는가”를 먼저 감각적으로 이해하는 것이다. 

문제 요약

항목	내용
입력	정점 개수 n, 원하는 리프 노드 개수 m
출력	조건을 만족하는 트리의 간선 n-1개
문제 핵심	트리를 직접 “구성”해서 리프 개수를 맞추는 것
중요 조건	트리는 연결되어 있어야 하고, 사이클이 없어야 하며, 간선 수는 정확히 n-1개여야 함

먼저 리프 노드부터 다시 확인하기

리프 노드는 연결된 간선이 정확히 1개인 정점이다. 즉, 트리의 끝점이라고 생각하면 된다.

예시: 일렬로 연결한 트리

0 - 1 - 2 - 3

이 경우 리프는 양 끝점인 0, 3 두 개다.

이 문제의 핵심 아이디어

이 문제는 트리를 “탐색”하는 문제가 아니라, 리프 개수가 원하는 값 m이 되도록 트리 모양을 설계하는 문제다.

여기서 중요한 감각은 아래 두 가지다.

1. 일렬로 길게 연결하면

리프는 항상 양 끝의 2개만 생긴다.

2. 한 정점에 새 정점을 붙이면

붙은 새 정점은 리프 1개가 된다.

구성 전략: 뼈대 + 추가 리프

가장 깔끔한 방법은 다음과 같다.

1단계

일부 정점을 일렬로 연결해서 트리의 뼈대를 만든다.

2단계

남은 정점들을 한 정점에 몰아서 붙인다.

3단계

그러면 붙인 정점 수만큼 리프 수를 조절할 수 있다.

핵심 구조

0 - 1 - 2 - 3 - ... - (k-1)
│
k
│
k+1, k+2, ...

실제 구현에서는 남은 정점들을 보통 1번 정점에 붙이면 된다.

왜 k = n - m + 2 인가?

뼈대로 사용하는 정점 수를 k라고 하자. 그러면 일렬 뼈대의 리프는 항상 2개다.

남은 정점 수는 n - k개이고, 이 정점들을 한 점에 하나씩 붙이면 전부 새로운 리프가 된다.

최종 리프 개수

2 + (n - k)

이 값을 우리가 원하는 리프 개수 m으로 맞추면 된다.

2 + (n - k) = m
2 + n - k = m
k = n - m + 2

예시로 이해하기: n = 7, m = 4

리프를 4개 만들고 싶다고 하자.

k = n - m + 2
k = 7 - 4 + 2 = 5

즉, 0부터 4까지 총 5개 정점을 뼈대로 일렬로 연결한다.

0 - 1 - 2 - 3 - 4

이 상태의 리프는 0, 4 두 개다.

남은 정점은 5, 6 이고, 이 둘을 1번 정점에 붙인다.

0 - 1 - 2 - 3 - 4
|
5
|
6

텍스트로 표현하면 5와 6이 1에 연결된다고 보면 된다.

정점	차수	리프 여부
0	1	리프
4	1	리프
5	1	리프
6	1	리프

최종 리프는 0, 4, 5, 6 총 4개가 되어 조건을 만족한다.

구현 순서 정리

1단계

n, m 입력 받기

2단계

k = n - m + 2 계산

3단계

0부터 k-1까지 일렬로 연결

4단계

k부터 n-1까지를 1번 정점에 연결

헷갈리기 쉬운 포인트

실수 포인트	왜 틀리나	올바른 처리
입력을 int(input().split())로 받는 경우	split 결과는 리스트라서 int를 바로 씌울 수 없음	n, m = map(int, input().split())
트리 노드 클래스를 만들려고 하는 경우	이 문제는 트리 탐색/구현 문제가 아니라 간선 출력 문제	간선만 바로 출력하면 충분
for i in range(k)로 뼈대를 만드는 경우	마지막에 없는 정점 k를 건드리게 됨	for i in range(k-1)
남은 정점 시작 번호를 잘못 잡는 경우	뼈대로 0부터 k-1까지 이미 사용했기 때문	남은 정점은 k부터 시작
k = n - m + 1처럼 계산하는 경우	뼈대 자체가 이미 리프 2개를 만든다는 점을 놓친 것	k = n - m + 2

정답 코드

n, m = map(int, input().split())

k = n - m + 2

# 0 ~ k-1 까지 일렬로 연결
for i in range(k - 1):
    print(i, i + 1)

# 남은 정점들을 1번 정점에 연결
for i in range(k, n):
    print(1, i)

코드가 왜 맞는가?

첫 번째 반복문은 뼈대 정점 k개를 일렬로 연결하므로 간선 k-1개를 만든다.

두 번째 반복문은 남은 정점 n-k개를 1번 정점에 붙이므로 간선 n-k개를 만든다.

전체 간선 수 = (k - 1) + (n - k) = n - 1

즉, 정확히 트리 조건을 만족한다.

마무리

이 문제는 트리 문제처럼 보이지만, 실제로는 리프 개수를 제어할 수 있는 구조를 떠올리는 구성 문제에 가깝다.

핵심은 “일렬 뼈대는 리프 2개를 만들고, 남는 정점은 붙일 때마다 리프 1개를 만든다”는 감각이다.

이 아이디어만 잡히면 구현은 아주 짧게 끝난다.