[BOJ] 6416 트리인가? - python

풀이

- 들어오는 간선이 하나도 없는 root 노드가 '단 한 개 ' 존재해야 한다.
- 루트를 제외한 모든 노드는 반드시 '단 하나의' 들어오는 간선이 존재한다.
- 노드가 존재하지 않는 것도 트리이다.
- Node = Edge + 1

1. 입력을 받아 각 테스트 케이스들을 treeList에 저장해 놓는다. 각 tree는 u가 key로, v가 value 리스트형으로 구성되어 있다.
   1. ex) { 1:[3], 4:[2,5] }
2. 나가는 엣지 노드들 U → keys() , 들어오는 엣지 노드들 V → values()로 리스트화 해둔다.

   keyList = list(aTree.keys()) #나가는 엣지 노드들 (u)
       valueList = list(aTree.values()) #들어오는 엣지 노드들 (v)
   
       #들어오는 엣지가 존재하는 노드들(value)
       totalValueList = []
       for value in valueList:
           totalValueList.extend(value)
       totalValueSet = set(totalValueList)
   ​

3. 트리임을 확인하는 조건들에 맞춰 조건을 확인한다.

a. 노드의 개수가 0개여도 트리다.

if len(totalKeyValue) == 0: #노드의 개수가 0개여도 트리이다.
        print("Case " + str(index) + " is a tree.")
        return

b. 들어오는 간선이 하나도 없는 root 노드가 단 한 개 존재해야 함

isRoot = 0
    for key in keyList:
        if key not in totalValueList: #only u이기만 한 노드 검사 (Root)
            isRoot += 1

if isRoot != 1: #only u인 루트 노드는 하나만 존재할 수 있다.
        print("Case "+str(index)+" is not a tree.")
        return

c. 들어오는 간선이 두 개 이상인 노드가 존재하는지 검사

if len(totalValueList) > len(totalValueSet): #v가 두 개 이상인 노드 존재하는지 검사
        print("Case "+str(index)+" is not a tree.")
        return

d. 이외는 정상적인 트리이다.

print("Case " + str(index) + " is a tree.") #이외의 것들

 

코드

import sys

def input():
    return sys.stdin.readline().rstrip()

treeList = []
tree = {}

while True:
    aline = input().split(" ")
    if aline[0] == '':
        continue
    if aline[0] == '-1':
        break
    for i in range(0,len(aline),3):
        if aline[i] == '0':
            treeList.append(tree)
            tree = {}
            break
        else:
            if aline[i] in tree:
                tree[aline[i]].append(aline[i+1])
            else:
                tree[aline[i]] = [aline[i + 1]]

def isTree(aTree,index):
    keyList = list(aTree.keys()) #나가는 엣지 노드들 (u)
    valueList = list(aTree.values()) #들어오는 엣지 노드들 (v)

    #들어오는 엣지가 존재하는 노드들(value)
    totalValueList = []
    for value in valueList:
        totalValueList.extend(value)
    totalValueSet = set(totalValueList)

    isRoot = 0
    for key in keyList:
        if key not in totalValueList: #only u이기만 한 노드 검사 (Root)
            isRoot += 1

    totalKeyValue = set(keyList).union(totalValueSet)
    
    if len(totalKeyValue) == 0: #노드의 개수가 0개여도 트리이다.
        print("Case " + str(index) + " is a tree.")
        return
    if isRoot != 1: #only u인 루트 노드는 하나만 존재할 수 있다.
        print("Case "+str(index)+" is not a tree.")
        return
    if len(totalValueList) > len(totalValueSet): #v가 두 개 이상인 노드 존재하는지 검사
        print("Case "+str(index)+" is not a tree.")
        return
    print("Case " + str(index) + " is a tree.") #이외의 것들

for i,aTree in enumerate(treeList):
    isTree(aTree,i+1)

 

얻어가는 것

• tree 성립 조건
• - 들어오는 간선이 하나도 없는 root 노드가 '단 한 개 ' 존재해야 한다. - 루트를 제외한 모든 노드는 반드시 '단 하나의' 들어오는 간선이 존재한다. - 노드가 존재하지 않는 것도 트리이다. - Node = Edge + 1
• 파이썬에서 tree 구현하기
• #트리 자료구조 선언 class Node: def __init__(self,data): self.left = None self.right = None self.data = data #트리 초기화 root = Node(10) root.left = Node(34) root.right = Node(89) root.left.left = Node(45) root.left.right = Node(50) 10 / \\ 34 89 / \\ 45 50

느낀점

"211207"

소요 시간 : 1h

• tree의 성립 조건에 대해 알 수 있었다.