[Python] 백준 14244 - 트리 만들기

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

문제

n과 m이 주어졌을 때, n개의 노드로 이루어져 있고, m개의 리프로 이루어져 있는 트리를 만드는 프로그램을 작성하시오.

항상 정답이 존재하는 경우만 입력으로 주어진다.

트리는 사이클이 없는 연결 그래프이고, 리프는 차수가 1인 노드를 의미한다.

입력

첫째 줄에 n과 m이 주어진다. (3 ≤ n ≤ 50, 2 ≤ m ≤ n-1)

출력

첫째 줄부터 n-1개의 줄에 트리의 간선 정보를 출력한다. 트리의 정점은 0번부터 n-1번까지 이다.

---

풀이

랜마에 떠서 풀게 된 실버 4 문제이다.

보통 트리를 탐색하는 문제를 풀어봤지 트리를 직접 조건에 만들어서 출력하는 문제는 처음 풀어보는데;;; 실버 4인만큼 도전해봤다

처음에는 살짝 어려울 것 같아서 당황했는데... 문제를 풀고 나니 스페셜 저지 만드는게 더 어려웠겠다 싶었다.

 

두 개의 노드를 연결하면 리프 노드(문제에서는 차수가 1인 노드를 전부 리프라고 정의했다)가 두 개 생긴다. 마찬가지로, 여러 개의 노드를 일직선으로 쭉 연결하면 리프 노드는 두 개 이다.

 

그렇게 노드들의 개수를 맞추어주고, 남은 몇 개의 노드들을 1번 노드에 붙여주는 식으로 리프 노드의 개수를 맞추어주면 된다.

 

예를 들어 n = 6, m = 4이라면,

위와 같이 n-m+1개의 선분을 만들어주고....(현재 리프 노드는 2개이다)

m-2(2개는 이미 만들어져있으므로) 개 만큼의 노드들을 1번에 연결해주면 된다. 0번에 연결해주면 리프 노드 하나가 사라지므로 1번에 연결한다. 따라서 다음과 같이 매우 짧게 코드를 작성할 수 있다.

n, m = map(int, input().split())
for i in range(n-m+1):
    print(i, i+1)

for i in range(m-2):
    print(1, n-m+2+i)