[Seop's의 코드풀이] 백준 6416 트리인가? - Python

이번에 풀어볼 문제는 백준 6416번 '트리인가?'라는 문제입니다.

문제는 다음과 같습니다.

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

6416번: 트리인가?

 

이번 문제는 문제에서 제시한 트리를 만족하는 조건을 잘 구현해 주면 된다.

편의상 들어오는 간선은 부모 노드, 나가는 간선은 자식 노드라고 하겠습니다. (위의 제일 왼쪽 트리에서  5의 자식 노드 : 3,6,2 , 6의 부모노드 : 5 )

1. 단 하나의 루트만 존재한다. -> 루트노드가 2개 이상 있으면 안된다 -> 부모가 없는 노드는 한개여야만 한다.

2. 루트를 제외하고 모든 노드들에게 들어오는 간선이 하나여야만 한다.  -> 루트를 제외하고 부모는 한개씩만 있어야 한다.

3. 루트에서 모든 노드들로 갈 수 있어야 한다. -> (모든 노드의 수 = 루트로 부터 뻗어나간 노드의 수 + 1) 이식이 성립되어야 한다.

4. 비어있어도 트리다.

 

위 4가지를 생각하면서 알고리즘을 작성하면 트리인지 아닌지는 분간 할 수 있을 것이라 생각된다.

추가로 이번 문제는 테스트케이스가 (-1, -1)등 음의 정수가 나오기 전까지 계속됨으로 이점에 유의하여야 한다.

 

전체적인 코드는 다음과 같으며 질문과 피드백은 언제나 감사드립니다.

 

import sys
input = sys.stdin.readline

class Node:
    def __init__(self, data):
        self.data = data
        self.child = None
        self.parant = None

    def __str__(self):
        return str(self.data)

    
def soluction() :

    def checkCycle(rootNode) :
        cnt = len(rootNode.child)
        for i in rootNode.child :
            cnt += checkCycle(node_dict[i])
        return cnt

    isInput = True
    answer = True
    node_dict = dict()
    root = None
    global isWorking

    while isInput :
        buf = input().rstrip().split("  ")
        if buf[0] == '' :
            continue
        for temp in buf :
            a, b = map(int , temp.split(" "))
            if a == 0 and b == 0 :
                isInput = False
                break
            elif a < 0 and b < 0:
                isWorking = False
                isInput = False
                break
            # node를 딕셔너리에 저장한다.
            if a in node_dict :
                node_dict[a].child.append(b)
            else :
                node_dict[a] = Node(a)
                node_dict[a].child = [b]
            if b in node_dict :
                # 부모가 2명(들어오는 간선의 수가 2개이면 안된다.)일 순 없다
                if node_dict[b].parant == None :
                    node_dict[b].parant = a
                else :
                    answer = False
            else :
                node_dict[b] = Node(b)
                node_dict[b].parant = a
                node_dict[b].child = []
    #  공배열도 트리이다.
    if len(node_dict) == 0 :
        return True
    if answer == False :
        return answer
    #  루트 노드 찾기 and 부모가 없는 노드가 2개이면 한개의 트리가 아니다.
    for v in node_dict.values() :
        if v.parant == None :
            if root == None :
                root = v.data
            else :
                answer = False
                return answer
    # 루트가 없어도 트리가 이나다.
    if root == None :
        return False

    #  루트로부터 시작해서 모든 노드로 갈 수 있어야 한다.
    cycle = 1 + len(node_dict[root].child)
    for i in node_dict[root].child :
        cycle += checkCycle(node_dict[i])
    if cycle != len(node_dict) :
        return False
    return answer


if __name__ == "__main__":
    isWorking = True
    num = 1
    while isWorking :
        check = soluction()
        if not isWorking :
            break
        if check :
            string = "Case " + str(num) + " is a tree."
            print(string)
        else :
            string = "Case " + str(num) + " is not a tree."
            print(string)
        num += 1