트리 만들기(백준 14244번)

♣ 문제

♣ 문제 이해

n은 총 노드의 수, m은 리프 노드의 수를 가리킨다. m개의 리프노드는 부모 노드와는 연결되어 있어야 하지만 자식 노드는 갖지 않는다. 따라서 부모와 연결된 노선만 존재한다. 

 

즉 n개의 노드가 주어지고, 리프 노드가 몇 개인지를 고려하여 노드들 사이의 노선을 완성하여 출력하면 되는 것이다. 

예를 들어 예제가 4  2 일 때 예제 출력이 0 1, 1 2, 2 3이다. 

 

위의 출력은 수많은 답 중 하나일 뿐이다(이 문제에는 스페셜 저지가 적용된다. 출력된 노선을 노드 사이에 그리면 0, 3 노드가 리프 노드이고, 1과 2는 그 외의 노드가 된다. 

 

답이 이렇게 나와도 된다. 위의 그림에서는 1과 2가 리프노드이고 0과 2는 그 외의 노드가 되는 것이다. 

 

 

♣ 해결 방법

처음에는 답이 하나만 있는 줄 알고 리프 노드를 어떻게 정하는지를 고민했는데 여러 가지 답이 있는 스페셜 저지 문제였다. 나는 아래와 같은 과정을 통해 문제를 풀었다. 

 

1. n개의 노드를 0, 1, 2, 3... n-1 노드라고 생각한다. 

2. n 개의 노드 중 0을 항상 첫 노드, 즉 연결을 주도하는 노드라고 생각한다. (마치 부모 노드처럼)

3. 0 노드를 제외하고 그 다음부터의 노드 중 m개를 0 노드에 연결한다. 예를 들어 입력이 5 3 이라면 

 

0이 맨 위의 부모 노드이고, 그 다음 노드 1부터 시작해서 m개를 리프 노드처럼 연결한다. 여기서는 m이 3이므로 1, 2, 3 노드 3개를 노드 0에 연결한다.