068 트리

첫번째 코드

 

먼저 tree의 구성을 리스트로 만들어야 하는데, 어떤 리스트로 작성할 것인지, 어떤 부분에 어떻게 들어갈 것인지 (양방향, 단방향)에 대해서 생각보아야 한다.

 

또한 DFS를 통해 계속해서 파고 들어가는 방법이고 해당 코드는 이전에 공부한 DFS의 코드와 비슷한 형태를 갖고 있다.

 

트리의 리프 노드를 확인하기 위해 cNode라는 것을 통해 cNode가 0이면 아래 연결된 노드가 없다는 의미로 해석되어 해당 노드는 리프 노드라는 의미이다.

 

위 과정을 통해 리프 노드의 개수를 확인한다.

 

아래 코드는 책을 참고하였고, 그래도 앞에 그래프보다는 할 수 있겠다..라는 생각이 든다..(과연이지만..)

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
visited = [False] * n
tree = [[] for _ in range(n)]
answer = 0
p = list(map(int, input().split()))
deleteNode = int(input())

for i in range(n):
    if p[i] != -1:
        tree[i].append(p[i])
        tree[p[i]].append(i)
    else:
        root = i

def DFS(number):
    global answer
    visited[number] = True
    cNode = 0
    for i in tree[number]:
        if not visited[i] and i != deleteNode:
            cNode += 1
            DFS(i)
    if cNode == 0:
        answer += 1

if deleteNode == root:
    print(0)
else:
    DFS(root)
    print(answer)

 

통과!

배낀다고 우울해하지 말기!! 실력은 늘고 있다!!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/1068.%E2%80%85%ED%8A%B8%EB%A6%AC

programmers/백준/Gold/1068. 트리 at main · ornni/programmers