BOJ 6415 - 트리인가?

문제

문제 풀러 가기

접근

이 문제를 풀 때 처음에는 트리를 순회하며 풀까 생각했었다. 그런데 문제에서 root노드가 주어지지 않기 때문에 순회하기 전에 root노드를 찾아야하지 않을까 생각했다. 그런데 문제 자체가 트리인지 아닌지를 판별하기만 하면 되었기에, 순회를 굳이 하지 않더라도 트리의 특징을 이용한다면 좀 더 쉽게 풀 수 있다고 생각이 들었다. 결국 나는 순회하는 방식이 아닌 트리의 특징을 이용한 방식으로 문제를 풀었다.

전에 트리의 특징에 대한 글을 적었는데 그 글을 참고해보면 좋겠다.(근데 사실 특징들을 문제에 아예 친절히 적어놨더라)

트리 특징
1. root노드는 반드시 1개만 존재하거나, 존재하지 않는다(아예 노드 자체가 없는 경우).
2. root노드에서 다른 임의의 노드로 가는 경로는 유일하다.
3. 노드의 갯수 -1 = 간선의 수

이에 나는 root, children 집합을 만들었다. root 집합은 시작 노드가 될 수 있는 노드들이 있는 집합이고, children 집합은 자식노드로 쓰이는 노드들이 있는 집합이다. 그리고 입력을 받으면서 조건에 따라 root 집합과 children 집합에 대한 연산을 하여 트리를 연결시켜나간다.

한 케이스에 대한 입력을 다 받았다면, 이제 트리를 판별하면 된다.
입력으로 들어온 노드가 1개 이상일 경우,
root집합에 꼭 하나의 노드만 존재하고, 간선의 갯수 + 1 = root집합의 크기 + children집합의 크기를 만족하면 트리이다.
입력으로 아무런 노드가 들어오지 않았다면, 그냥 그대로 트리를 만족한다.
이 조건에 따라 트리의 특징들과 부합하는지를 확인하고 답을 출력하면 된다.

* 이 문제는 입력처리가 까다로웠다.. 맘 편하고자 느린걸 알면서도 Scanner를 썼다...ㅎㅎ

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        boolean flag = true;
        int caseN = 0; // 몇 번째 나무인지 기록

        while(flag){
            HashSet<Integer> root = new HashSet<Integer>();
            HashSet<Integer> children = new HashSet<Integer>();
            int total = 0, u, v; //total은 간선의 갯수
            boolean isTree = true;
            while(0 <= caseN){
                u = sc.nextInt();
                v = sc.nextInt();
                if(u ==-1 && v == -1) { 
                // -1 -1이 들어오면 flag값을 바꾸어 탈출
                    flag = false;
                    break;
                }
                if(u == 0 && v == 0 ) {
                    // tree 판별
                    caseN++;
                    if(1 < root.size() || (total+1) != root.size() + children.size() )
                    // root가 2개 이상이거나, 간선의 갯수가 노드-1이 아닐 때 - 트리가 아님
                        isTree = false;
                    if( isTree || total== 0) 
                    // total = 0 은 노드가 아예 없는 트리 
                    sb.append("Case "+caseN + " is a tree.\n");
                    else sb.append("Case "+caseN + " is not a tree.\n");
                    break;
                }
                else if(isTree) { // 아직까지 n번째 트리가 트리임이 유효할 때
                    total++; //간선의 갯수를 늘림
                    if(!children.contains(u)) root.add(u); //root은 일단 넣고 누군가의 자식노드(들어오는 노드)가 될 때 뺀다.
                    if(children.contains(v)) isTree = false; // 해당 노드로 들어오는 간선이 두 개이상이 되었으므로 더이상 트리가 아니다.
                    else{
                        if(root.contains(v)) root.remove(v); // 이전에 root였다면 이제는 누군가의 자식노드가 되었으므로 root집합에서 제외한다.
                        children.add(v); //자식노드로 슝 넣어준다.
                    }
                }
            }
        }
        System.out.println(sb);
    }
}