[BOJ_6416] 트리인가?

설명

---

트리에 대해서 별도의 이해가 없었고 이때, 문제의 구현을 위한 설명만을 보고 풀었다. 그리고, 설명 게시판을 많이 참고하였는데 이 문제는 들어오는 간선이 1개 이상이고 간선이 아예 없는 루트 노드 하나가 존재하는 것을 찾아야 한다.

 

그런데 어이가 없던 것이 이렇게 구현을 하고 아무리 돌려도 틀렸습니다가 떠서 질문 게시판을 다시 봤더니 0 0인 케이스도 가능하다고 한다. 즉, 아무 노드가 없을때도 트리가 된다고 한다.

 

아무리 찾아봐도 잘 모르겠어서 chatGPT를 돌려서 트리에도 공집합 같은 트리가 존재하는지 봤더니 아래와 같은 답변을 얻었다.

 

공 트리는 트리가 아무런 노드도 가지고 있지 않은 경우를 가리킵니다. 즉, 노드가 존재하지 않고 아무런 관계도 형성되지 않은 상태를 말합니다. 이는 일종의 트리이지만 아무런 정보도 포함하고 있지 않으며, 사용 상황에 따라서는 유효한 경우가 있을 수 있습니다.

 공 트리는 트리 자체의 정의에서도 허용되는 경우일 수 있으며, 예를 들어 트리 구조를 동적으로 생성하는 과정에서 아무 노드도 추가되지 않은 초기 상태를 나타낼 때 사용될 수 있습니다. 따라서 공 트리는 일종의 특수한 경우이며, 트리의 일반적인 정의에서도 허용될 수 있습니다.

 

 

이래서 0 0만 넣은 케이스도 트리가 되는구나 싶기도 했다... 좀 더 상세히 트리의 정의에 대해서 공부를 해야겠다.

 

코드

---

package tree;

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

public class BOJ_6416 {
    static List<Integer> inputCase;
    private static void Input(Scanner sc){
        inputCase = new ArrayList<>();
        while (true){
            int u = sc.nextInt();
            int v = sc.nextInt();
            if(u == -1 && v == -1){
                System.exit(0);
            }else if (u == 0 && v == 0){
                inputCase.add(u);
                inputCase.add(v);
                break;
            }
            else{
                inputCase.add(u);
                inputCase.add(v);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        int caseNumber = 1;
        Scanner sc = new Scanner(System.in);
        while (true) {
            Input(sc);
            Map<Integer, Integer> inDegree = new HashMap<>();
            Set<Integer> nodes = new HashSet<>();
            boolean isTree = true;

            for (int i = 0; i < inputCase.size(); i+=2) {
                int u = inputCase.get(i);
                int v = inputCase.get(i+1);

                if (u == 0 && v == 0) {
                    break;
                }

                // 간선 정보 저장
                nodes.add(u);
                nodes.add(v);

                // 들어오는 간선 개수 체크
                inDegree.put(v, inDegree.getOrDefault(v, 0) + 1);

                // 그래프가 순환 구조인 경우
                if (inDegree.get(v) > 1) {
                    isTree = false;
                }
            }

            // 루트 노드 찾기
            int rootCount = 0;
            int rootNode = 0;
            for (int node : nodes) {
                if (!inDegree.containsKey(node)) {
                    rootCount++;
                    rootNode = node;
                }
            }

            // 루트 노드가 하나가 아니거나 없는 경우
            if (rootCount != 1) {
                isTree = false;
            }

            //노드가 아예 없는 경우 트리가 될 수 있다고 한다.
            if(inDegree.size() == 0){
                isTree = true;
            }

            // 트리인지 출력
            if (isTree) {
                System.out.println("Case " + caseNumber + " is a tree.");
            } else {
                System.out.println("Case " + caseNumber + " is not a tree.");
            }

            caseNumber++;
        }
    }
}

 

6416번: 트리인가?