[트리] 백준 6416 트리인가?

6416번: 트리인가?

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

 

# 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 출력을 위한 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 공백과 개행을 기준으로 쉽게 입력받기 위한 Scanner
        Scanner sc = new Scanner(System.in);

        // <정점, 진입 간선의 개수> 를 담는 map
        HashMap<Integer, Integer> map;

        // k번째 테스트 케이스
        int k = 1;

        while (true) {
            map = new HashMap<>();

            // 간선의 개수 edge
            int edge = 0;
            while (true) {
                // 화살표의 방향은 start -> end
                int start = sc.nextInt();
                int end = sc.nextInt();

                // 0, 0인 경우 하나의 테스트 케이스 입력 종료
                // -1, -1인 경우 main() 종료
                if (start == 0 && end == 0) break;
                if (start == -1 && end == -1) return;

                // start는 진입 간선이 추가되지 않으므로 value를 그대로 두고 end는 +1 하기
                map.put(start, map.getOrDefault(start, 0));
                map.put(end, map.getOrDefault(end, 0) + 1);

                edge++;
            }

            // 루트의 개수 root
            int root = 0;

            // 진입 간선의 수가 1보다 큰 노드가 있다면 false로 바꿀 isTrue
            boolean isTrue = true;

            Iterator<Integer> key = map.keySet().iterator();
            while (key.hasNext()) {
                // key를 하나씩 가져오기
                int num = key.next();

                if (map.get(num) == 0) {
                    // 가져온 키의 value가 0이면 root++
                    root++;
                } else if(map.get(num) > 1) {
                    // 가져온 키의 value가 1보다 크면 isTrue를 false로 지정하고 break
                    // (진입 간선의 수가 1보다 큰 노드가 하나라도 있다면 트리가 아니기 때문)
                    isTrue = false;
                    break;
                }
            }

            if (map.size() == 0) {
                // 0, 0이 입력되어도 (=map의 size가 0이어도) 빈 트리이므로 트리라고 출력
                bw.write("Case " +  String.valueOf(k) + " is a tree.\n");
            }
            else if (root == 1 && isTrue && (map.size() - 1) == edge) {
                // root의 개수가 1개 && 루트를 제외한 모든 노드의 진입 간선이 1개 && 정점의 개수-1 == 간선의 개수 이면 트리라고 출력
                bw.write("Case " +  String.valueOf(k) + " is a tree.\n");
            } else {
                // 이외의 경우는 모두 트리가 아님
                bw.write("Case " +  String.valueOf(k) + " is not a tree.\n");
            }
            k++;

            bw.flush();
        }
    }
}

• 트리의 첫 문제를 6416으로 맞이해 개인적으로 이해에도 시간이 오래 걸렸던 문제였다. 하지만 차분히 풀었다면 스스로의 힘으로 가능했을 것도 같기도... 아닌거 같기도...... 매일 코테 문제를 푸는게 생각보다 쉽지 않다.
• cf) bw.flush(); 빼먹지 말기 (오답처리됨)

 

트리 판별 기준

1. 루트의 개수가 1개
2. 루트를 제외한 모든 노드의 진입 간선이 1개
3. 정점의 개수 - 1 == 간선의 개수

이외의 경우는 모두 트리가 아니다.

 

코드는 아래 블로그를 참고했다.

[백준]6416: 트리인가? - JAVA