[백준] 14244번: 트리 만들기 (python)

14244번: 트리 만들기

---

문제 )

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

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

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

 

 

입력 :

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

 

출력 :

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

 

 

 

풀이)

처음에 문제 이해를 못해서 시간을 상당히 많이 잡아먹었다.

예제를 이용하여 내가 이해한 것을 말해보자면,

 

예제 1)

4 2

---

예제 2)

4 3

 

 

---

예제 3)

3 2

---

예제 3)

5 3

---

 

그림과 같이 리프는 최소 2개가 생성되며,

그 이상일 경우에는  m - 1개까지 1번 노드에 리프를 생성한 후,

m번 노드를 기점으로 가지를 하나 길게 형성해 주는 방법으로 리프를 1개 더 만들어주었다.

생각은 이러했지만, 코드가 생각보다 깔끔하게 나오지 않고 하드코딩으로 나오게 되었다.

내가 짠 코드는 다음과 같다.  

 

n, m = map(int, input().split())
 
if m == 2:
    for i in range(n - 1):
        print(i, i + 1)
 
else: # m이 3 이상
    print("0 1")
    for i in range(2, m + 1):
        print(1, i)
    for j in range(m, n - 1):
        print(j, j + 1)

정답이 맞긴 하나 코드가 좀 불편해, 다른 사람의 코드도 찾아보았다.

 

n, m = map(int, input().split())
 
# 리프의 개수
leaf = 0
if m == 2:
    leaf = 1  # 중심 노드를 리프로 포함
 
last_leaf = 0
for i in range(1, n):
    if m > leaf:
        print(0, i)
        leaf += 1
    else:
        print(last_leaf, i)
    last_leaf = i

 

확실히 구현쪽에서는 갈 길이 먼 것 같다.

---

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

14244번: 트리 만들기