[백준] 1068번 - 트리 (파이썬)

문제) 백준 - 그래프 이론/트리 - 트리

-> www.acmicpc.net/problem/1068

1068번: 트리

 

1. 인접 행렬 방식으로 graph를 False로 초기화한다.

2. 입력으로 들어온 부모 노드들의 정보를 이용해 graph의 연결을 채워주고 root를 선정한다.

3. 세 번째 줄 입력에 나오는 지울 노드의 모든 연결을 끊어준다.(False로 설정) 

4. dfs로 root부터 탐색해 리프 노드 개수를 구해준다.

 

 

반성)

트리 문제라 생각해서 인접 행렬의 활용과 dfs의 접근을 생각 못했다.

 

 

소스 코드)

import sys
input = sys.stdin.readline

def dfs(root):
    global cnt
    switch = False
    visited[root] = True
    for i in range(n):
        if not visited[i] and graph[root][i]:
            switch = True
            dfs(i)
    if not switch:
        cnt += 1


n = int(input())
info = list(map(int, input().split()))
del_node = int(input())

graph = [[False] * n for _ in range(n)]
visited = [False] * n
cnt = 0

for i in range(n):
    if info[i] != -1:
        graph[i][info[i]] = True
        graph[info[i]][i] = True
    else:
        root = i

for i in range(n):
    graph[i][del_node] = False
    graph[del_node][i] = False

dfs(root)

if del_node == root:
    print(0)
else:
    print(cnt)