[백준 1068] 트리 (python)

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

1068번: 트리

(맨 밑에 수정본이 있습니다. 끝까지 읽어주시면 감사드리겠습니다 👍👍 (수정 : 2021-02-09))

후.. 이 문제를 풀고 내가 많이 부족하다고 느꼈다.

 

자료구조 트리로 다시 풀고, dfs도 정의도 확실히 공부할 것이다.

 

또한 if else문으로써 자료형이나 초기화된 값을 사용하는 것이 올바른 방법인지에 대한 고민을 하고, 만약 올바르다고 판단될 경우 나만의 방법을 확립할 예정이다.

 

 

import sys
 
def dfs_leaf_find(Tree_,leaf,count):
    if Tree_[leaf] !=-3:
        if len(Tree_[leaf]) > 1 :
            for i in range(len(Tree_[leaf])):
                count = dfs_leaf_find(Tree_, Tree_[leaf][i],count)
        else:
            count = dfs_leaf_find(Tree_, Tree_[leaf][0],count)
    else:
        count += 1
    return count
 
def dfs(Tree_, leaf):
    if Tree_[leaf] !=-3:
        if len(Tree_[leaf]) == 2 :
            Tree_ = dfs(Tree_, Tree_[leaf][0])
            Tree_ = dfs(Tree_, Tree_[leaf][1])
        else:
            Tree_ = dfs(Tree_, Tree_[leaf][0])
    Tree_[leaf] = -3
 
    return Tree_
 
N = int(input())
li = list(map(int,sys.stdin.readline().split()))
leaf_ = int(input())
 
Tree_ = [-3 for _ in range(50)]
for i in range(len(li)):
    if li[i] == -1:
        root = i
    if Tree_[li[i]] == -3:
        Tree_[li[i]] = [i]
    else:
        Tree_[li[i]].append(i)
 
if root == leaf_:
    print(0)
 
 
else:
    # del
    if Tree_[leaf_] != -3:
        ans = dfs(Tree_, leaf_)
    else:
        ans = Tree_
    for i in range(len(Tree_)):
        if Tree_[i] != -3:
            if leaf_ in Tree_[i]:
                if len(Tree_[i]) > 1:
                    for j in range(len(Tree_[i])):
                        if leaf_ == Tree_[i][j]:
                            del Tree_[i][j]
                            break
                else:
                    Tree_[i] = -3
    if Tree_[root] == -3:
        print(1)
    else:
        print(dfs_leaf_find(Tree_,root,0))

 

 

 

==== 수정 (2021-02-09 (화)) ====

 

거의 7달 전에 풀었던 문제인데, 검색어에 꽤나 상단에 있어서 다시 풀고 수정합니다 !

 

이번에 풀 때는 인접 리스트 방식을 이용해서 풀었는데요. 이차원 리스트를 만들어서 자신의 자식 노드의 번호를 자신의 번호의 인덱스 부분에 append하는 방식으로 구성했습니다. 부모 노드에서부터 자식노드로 내려가면서 저희가 자르고자 하는 자식노드를 찾으면, 그 자식노드의 정보를 없애기만 한다면 Leaf Node를 찾을 때는 없는 정보이기 때문에 정답을 구할 수 있을 것이라 생각했습니다.

 

 

import sys
 
N = int(input())
li = list(map(int, sys.stdin.readline().split()))
D_N = int(input()) #will delete node
tree = [[] for _ in range(N + 2)]
ans = 0
for i in range(len(li)):
    if (li[i] == -1):
        tree[N + 1].append(i) #루트를 N + 1로 둔다.
    else:
        tree[li[i]].append(i)
 
def dfs(n):
    global ans
    if (not len(tree[n])):
        ans += 1
        return
    for i in range(len(tree[n])):
        if (tree[n][i] == D_N):
            if (len(tree[n]) == 1):
                ans += 1
                return
            else:
                continue
        else:
            dfs(tree[n][i])
 
if (li[D_N] == -1):
    print(0)
else:
    dfs(N + 1)
    print(ans)