[백준] 트리인가? (6416) Java

문제 링크

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

6416번: 트리인가?

 

문제 요약

트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 한다. 이때, 노드 u에서 노드 v로 가는 간선이 존재하면 간선을 u에 대해서는 '나가는 간선', v에 대해서는 '들어오는 간선'이라고 하자.

1. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 루트(root) 노드라고 부른다.
2. 루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재한다.
3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 이는 루트를 제외한 모든 노드에 성립해야 한다.

아래의 그림을 보자. 원은 노드, 화살표는 간선을 의미하며, 화살표의 방향이 노드 u에서 노드 v로 향하는 경우 이는 이 간선이 u에서 나가는 간선이며 v로 들어오는 간선이다. 3개의 그림 중 앞의 2개는 트리지만 뒤의 1개는 트리가 아니다.

당신은 간선의 정보들을 받아서 해당 케이스가 트리인지를 판별해야 한다.

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 입력의 끝에는 두 개의 음의 정수가 주어진다.

각 테스트 케이스는 여러 개의 정수쌍으로 이루어져 있으며, 테스트 케이스의 끝에는 두 개의 0이 주어진다.

각 정수쌍 u, v에 대해서 이는 노드 u에서 노드 v로 가는 간선이 존재함을 의미한다. u와 v는 0보다 크다.

 

출력

각 테스트 케이스에 대해서, 테스트 케이스의 번호가 k일 때(k는 1부터 시작하며, 1씩 증가한다) 트리일 경우 "Case k is a tree."를, 트리가 아닐 경우 "Case k is not a tree."를 출력한다.

 

접근법

트리의 성질만 알면 매우 쉽게 풀 수 있는 문제이다.

사실상 알고리즘 문제가 아니라, 트리의 성질을 복습하는 문제라고 할 수 있다.

 

아무튼 주어진 그래프가 트리인지 확인하려면, 각 노드의 indegree 값만 확인해주면 끝이다.

indegree는 해당 노드로 들어오는 edge의 개수를 의미한다.

 

노드의 숫자 범위도 주어지지 않고, 특정한 순서대로 입력이 들어온다는 조건도 없으므로 HashMap으로 입력을 받았다.

 

key는 노드, value는 indegree로 하는 HashMap으로 각 노드에 대한 indegree를 저장한다.

그리고 HashMap의 모든 indegree 값에 대해서 반복을 돌면서

1. root (indegree가 0인 노드)가 "단 한개"만 존재하는지

2. indegree 값이 1보다 큰 노드가 존재하는지

이 조건만 확인하면 된다.

 

이 조건만 만족하면, 문제에서 주어진 경로에 대한 조건도 자연스럽게 만족하는데, 그 이유는 다음과 같다.

Root 노드에서 Node 3으로 향하는 유일한 경로만 존재하는 트리가 있다고 해보자.

만약 여기서 다른 경로를 추가한다고 하면, Root에서 Node3 까지의 경로에 존재하는 노드에 Root로부터 출발하는 어떤 경로를 추가해주면 된다. 근데 그러기 위해서는 Node1, Node2, Node3 중 반드시 하나의 노드의 indegree가 1보다 커져야만 가능하다.

따라서 indegree가 1보다 큰 노드가 존재하는지만 체크해주면, 유일한 경로에 대한 조건도 만족하게 된다.

 

이 외에도 자기 자신으로 이어지는 edge 같은 특수한 경우도 다 고려가 된다.

 

 

시간 복잡도

O(N). N은 노드의 개수.

오히려 입력 처리가 실제 알고리즘보다 더 오래걸린다.

 

 

공간 복잡도

N개의 indegree만 저장하면 된다.  N * 4 bytes 정도 된다.

 

 

풀면서 놓쳤던 점

입력 데이터 형태가 좀 이상해서 그런지

문제는 진작에 풀었는데 채점을 받으니까 런타임 에러가 떠서 30분 넘게 삽질을 했다.

 

기존에는 BufferedReader와 StringTokenizer를 썼는데

NullPointerException이 계속 발생해서  결국엔 Scanner를 썼다.

자바는 이런 부분이 좀 까다로운 것 같다.

 

 

이 문제에서 얻어갈 점

트리의 성질. 그래프.

 

 

코드

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        //각 node의 indegree를 저장할 map. key: node - value: indegree 형태.
        HashMap<Integer, Integer> indegreeMap = new HashMap<>();

        int caseNum = 1;
        boolean finish = false;

        //n개의 case에 대한 반복문
        while (true) {

            //(0,0)이 나올 떄 까지 (한 case가 끝날 때까지) indegree를 입력받는 함수
            //(-1, -1)을 입력받으면 true를 return함
            finish = getIndegree(indegreeMap, sc);

            if (finish)
                break;

            //indegree 정보를 가지고 tree인지 판단함
            if (isTree(indegreeMap))
                sb.append("Case " + caseNum + " is a tree.\n");
            else
                sb.append("Case " + caseNum + " is not a tree.\n");

            caseNum++;
            indegreeMap.clear();
        }

        System.out.print(sb);
    }

    static boolean isTree(HashMap<Integer, Integer> indegreeMap)
    {
        boolean hasRoot = false;

        //node가 없어도 tree이다
        if (indegreeMap.size() == 0)
            return true;

        //모든 node의 indegree를 확인한다.
        for (Integer indegree : indegreeMap.values())
        {
            //indegree가 0인 node를 발견하면 root이다.
            if (indegree == 0)
            {
                //이미 root를 발견했는데 또 발견한 경우. tree가 아니므로 false return
                if (hasRoot)
                    return false;
                else
                    hasRoot = true;
            }
            //indegree가 1보다 크면 tree가 아니다.
            //이 부분에서 유일한 경로에 대한 조건도 따질 수 있다.
            else if (indegree > 1)
                return false;
        }

        //root가 아예 존재하지 않는 경우도 있음 (예: 하나의 cycle만 있는 graph)
        //그 경우도 역시 tree가 아니다
        return hasRoot;
    }

    static boolean getIndegree(HashMap<Integer, Integer> indegreeMap, Scanner sc)
    {
        int startNode, endNode;
        boolean finish = false;

        while (true) {
            startNode = sc.nextInt();
            endNode = sc.nextInt();

            //case에 대한 입력이 끝난 경우
            if (startNode == 0 && endNode == 0)
                break;

            //전체 프로그램에 대한 입력이 끝난 경우
            if (startNode == -1 && endNode == -1)
            {
                finish = true;
                break;
            }

            //edge가 출발하는 node는 indegree가 증가하지 않음
            //단 node가 존재한다는 것을 알고 있어야 하므로 (예를 들어 root node의 경우)
            //indegree가 0이 되게 map에 저장
            indegreeMap.putIfAbsent(startNode, 0);

            //edge가 도달하는 node는 indegree가 1 증가해야 한다.
            indegreeMap.putIfAbsent(endNode, 0);
            indegreeMap.put(endNode, indegreeMap.get(endNode) + 1);
        }

        return finish;
    }
}