#14244 : 트리 만들기

풀이방법

 

2023.05.15

이해하기가 조금 어렵지만, 이해하고 나면 구현하기 매우 쉬운 문제이다.

트리를 구현할 필요는 없다. 트리의 개념을 잘 이해하기만 하면 간단한 반복문 및 조건문으로 해결할 수 있다.

 

푸는 방법은 여러 가지가 있는데, 내가 사용한 방법만 설명하겠다.

 

리프가 2개여야 하는 경우와 리프가 3개 이상이어야 하는 경우로 나누어서 풀었다.

 

먼저, 리프가 2개인 경우, 모든 노드가 일직선으로 연결되어야 한다. 사이클을 만들 수 없으므로 리프가 2개일 수 있는 경우는 딱 이 경우 하나밖에 없다.

리프가 3개인 경우 트리를 만드는 방법은 매우 다양해지는데, 여러 방법 중 내가 선택한 것은 다음과 같다.

0번 노드를 중심으로 두고, 필요한 리프 개수만큼의 노드를 0번 노드에 따로따로 연결해준다.

그렇게 하면, 트리는 마치 문어발 같은 형태가 되고, 충족해야 할 리프 개수를 다 충족하게 된다.

여기까지 했는데 만약 아직 붙여야 할 노드가 남아있다면?? 리프 개수는 유지하면서 노드만 붙여야 한다. 어떻게 하면 될까? 존재하는 리프에 길게 노드를 이어붙이면 된다!

 

예시를 들어 살펴보자.

 

리프가 2개인 경우의 예시

입력값이 4 2 라고 한다면, 가능한 그래프의 형태는 이것밖에 없다.

0 1 2 3 순서로 잇든… 2 1 3 0 순서로 잇든… 다 정답 처리가 되도록 채점이 되는 문제이니 어떻게 이어붙이든 상관은 없다.

그러니 우리가 가장 편한 방법으로, 0 1 2 3 으로 붙이자!

그럼 출력값은 다음과 같다.

 

0 1

1 2

2 3

 

입력값이 5 2 라면 이렇게 하면 된다.

입력값이 6 2 라면 이렇게 하면 된다.

 

즉, 0번 노드가 첫 번째 리프의 역할을 하고

번호가 가장 큰 다른 노드 하나가 두 번째 리프의 역할을 하도록 만드는 풀이법이다.

 

리프가 3개 이상인 경우의 예시

리프가 3개 이상인 경우엔, 0번 노드가 리프가 아닌 중심이라고 생각하면 정답 그래프를 도출하기 편하다.

 

아래와 같이 0번 노드가 있다.

입력값이 5 3 이라고 하자.

그럼 일단, 3개의 리프가 중심에서 뻗어나오는 형태부터 완성해준다.

리프 3개가 완성되었다!

 

근데, 있어야 하는 노드가 총 5개이기 때문에,

리프의 개수는 그대로 유지하면서 한 개의 노드를 추가로 붙여주어야 한다.

 

어떻게 해야 할까?

존재하는 리프 (1, 2, 3번 노드) 중에 하나를 골라 그 끝에 이어붙여주면 된다!

 

셋 중 어느 것에 붙여도 상관없다.

우리는 가장 번호가 큰 노드에 붙이기로 하자.

그럼 다음과 같이 그래프가 완성된다.

노드는 5개, 리프는 3개이다.

 

그럼 출력은 다음과 같다.

 

0 1

0 2

0 3

3 4

 

만약 입력값이 6 3 이라면 다음과 같은 그래프를 만들면 된다.

입력값이 7 3 이라면 다음과 같은 그래프를 만들면 된다.

 

 

 

코드

Java(2023.05.15)

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner (System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		// 현재까지 만들어진 리프의 개수
		int cur = 0;
		
		// 필요한 리프가 2개인 경우, 0번 노드도 리프 취급
		if (m==2) cur = 1;
		
		// 가장 최근에 붙인 노드의 번호
		int lastLeaf = 0;
		
		// 그래프 만들기
		for (int i=1; i<n; i++) { // N개 노드를 다 붙일 때까지
			if (m > cur) { // M개의 리프가 만들어지기 전인 경우
				// 리프 하나 추가
				System.out.println(0 + " "  +i);
				cur++;
			}
			// 이미 M개 리프가 다 만들어진 이후인 경우
			// 마지막에 붙인 노드에 줄줄이 이어붙이기
			else System.out.println(lastLeaf + " " + i);
			// 마지막에 붙인 노드 번호 갱신
			lastLeaf = i;
		}
		
		
		sc.close();

	}

}