백준 6416 트리인가? Kotlin (트리)

문제 출처 : 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."를 출력한다.

알고리즘 분류

• 그래프 이론
• 트리

풀이

하.. 문제 조건들이 스트레스 받는다. 입력부터 맘에 안 든다.

우선 노드 번호의 최댓값은 주어지지 않았고, 게시판을 보면 최대 13이라고 직접 구해주신 분들이 있다.

이왕 구해주셨는데 ㅎㅎ 또 이용을 해줘야 하지 않겠는가

노드 번호의 최댓값을 13으로 잡고 하자.

 

문제에서 우리가 찾아야할 트리가 아닌 경우를 찾기 위한 조건들은 다음과 같다.

1. 트리는 정점의 개수가 간선의 개수보다 하나 더 많아야 한다. 

2.1. inDegree(진입 차수)가 하나도 없는 루트 노드가 여러 개 있으면 트리가 아니다.

2.2. 위를 찾기 위해 현재 테스트케이스에서 사용한 노드들을 저장해놓아야 한다.

3. inDegree가 두 개 이상이면 트리가 아니다.

 

이 조건들에 맞게 적절하게 분기 처리만 하면 된다!

라벨은 굳이 안 써도 되는데, 수정하다가 남은 잔해이다.

코드

import java.util.*
val br = System.`in`.bufferedReader()

fun main() = with(System.out.bufferedWriter()) {
    var t = 1
    var twoEdge=false
    val inDegree = IntArray(14)
    val visited = BooleanArray(14)
    var isFirstZero = true
    val set = HashSet<Int>()
    var edgeCnt=0
    loop@ while (true) {
        val tk = StringTokenizer(br.readLine())

        while (tk.hasMoreTokens()) {
            val from = tk.nextToken().toInt()
            val to = tk.nextToken().toInt()

            //프로그램 종료
            if (from == -1) {
                close()
                return;
            }
            //이미 진입 차수가 있는 경우
            if (inDegree[to] == 1) {
                twoEdge=true
                continue@loop
            }
            inDegree[to]++
            //테스트케이스 종료
            if (from == 0 && to == 0) {
                var root = 0
                for (i in 0 until 14) {
                    if (inDegree[i] == 0 && set.contains(i)) {
                        root++
                    }
                }
                if(isFirstZero){
                    write("Case $t is a tree.\n")
                }
                else {
                    if (root == 0 || twoEdge || set.size-1!=edgeCnt) {
                        write("Case $t is not a tree.\n")
                    } else {
                        write("Case $t is a tree.\n")
                    }
                }
                //reset
                isFirstZero=true
                twoEdge=false
                set.clear()
                t++
                edgeCnt=0
                for(i in 0 until 14){
                    inDegree[i]=0
                    visited[i]=false
                }
                continue@loop
            }
            set.add(from)
            set.add(to)
            edgeCnt++
            isFirstZero=false
        }
    }

    close()
}