[BOJ] 백준 14244. 트리 만들기

문제

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

 

---

풀이

트리의 개념을 활용한 구현 문제입니다.

 

 이 문제에서 리프란, 간선이 하나밖에 없는 노드입니다. 그래서 트리의 끝만 포함되는 것이 아니라, 조건이 맞다면 루트도 포함될 수 있습니다.

 

 소스 코드의 주석으로 풀이를 대체하겠습니다.

 

---

소스 코드

import java.util.Scanner;

public class B14244_트리만들기 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();

        int leafCount = 0; //리프 개수
        if(M==2) leafCount = 1; //M이 2라면,리프가 1개 뿐인 경우다.

        int lastLeafIdx = 0; 
        for(int i =1;i<N;i++){  // 여기서 i는 노드의 idx임.
            if(M>leafCount){ //리프 개수가 M보다 작으면
                leafCount+=1; // 현재의 노드 i를 새 리프로 추가
                System.out.println(0+" "+i);
            }
            else{ //리프 개수가 M보다 크거나 같으면
                // 마지막에 추가한 리프에 현재의 노드 idx를 연결
                System.out.println(lastLeafIdx+" "+i);
            }
            lastLeafIdx = i; //마지막 추가 리프 업데이트
        }
    }
}