[Python] BOJ 1068 - 트리

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

1068번: 트리

# 기본적인 트리문제이다.

# 일반적인 대학생들이라면, 자료구조 시간에 트리에 대해서 배웠을 텐데, 나는 자료구조수업을 듣지 않은

     채로 독학해서 알고리즘을 공부했고 트리를 대충 보고 넘어가서 아직은 낯선 주제이다.

# 그래도 그림그려가며 dfs, 재귀로 풀어보니 그렇게 어렵지는 않았다.

 

 

1. delete노드를 지웠을때 남는 Leaf 노드의 개수를 출력하는 문제이다.

 

2. tree에 각 노드의 부모노드를 저장한 뒤, delete로 지울 노드를 입력받는다.

      dfs함수에서 리프노드를 찾기위해 visited배열을 초기화해준다.

 

3. tree배열안에서 반복문을 돌며 graph[tree[i]]에 i를 append해준다.

      이 때, 만약 tree[i]가 delete이거나 i가 delete이면 continue를 통해 지워야 할 노드를

      애초에 graph를 만들때부터 넣어주지 않는다.

      또한 tree[i]가 -1이면 루트노드이므로 root에 i를 넣어준다.

 

4. 만약 delete가 root노드라면 0을 출력하고 아니면 dfs(root)를 실행한다.

      dfs함수: root노드를 시작으로 dfs함수로 연결된 노드들을 쭉 확인해준다.

                   현재 노드 s를 방문처리하고 만약 다음 노드 s의 자식노드가 없다면 not graph[s]

                   그 노드가 리프노드이므로 cnt를 1증가시킨다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(s):
    global cnt
    visited[s] = True
    if not graph[s]:
        cnt += 1

    for i in graph[s]:
        if not visited[i]:
            dfs(i)

N = int(input())
graph = [[] for _ in range(N)]
tree = list(map(int,input().split()))
delete = int(input())
visited = [False] * N
for i in range(N):
    if tree[i] == -1:
        root = i
    else:
        if tree[i] == delete or i == delete:
            continue
        else:
            graph[tree[i]].append(i)

if delete == root:
    print(0)
else:
    cnt = 0
    dfs(root)
    print(cnt)

(solved.ac 티어: 골드 5)