[백준] 1068 파이썬 - 트리

문제

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

 

풀이

입력 값에 따라 graph 배열을 선언해주었다.

인덱스는 노드의 숫자를, 원소 값은 해당 노드가 가진 자식 노드들의 리스트로 선언하였다.

 

이후 지워질 노드들을 dfs 탐색으로 구해주고, 

graph에서 해당 원소들을 지워주었다.

 

이후 dfs를 통해 그래프를 탐색하여, 더 이상 자식노드를 가지고 있지 않은 노드(리프노드)의 개수를 구해주었다.

 

코드

import sys

input = sys.stdin.readline
n = int(input())
array = list(map(int,input().split()))

graph = [[] for _ in range(n)]

root_node = 0
for i in range(n):
    # 루트 노드가 아니면
    if array[i] != -1:
        graph[array[i]].append(i)
    else:
        root_node = i

# 지워질 노드들 구하는 함수
def delete_dfs(graph,delete_node):
    global delete_nodes
    for i in graph[delete_node]:
        delete_nodes.add(i)
        delete_dfs(graph,i)

global delete_nodes
delete_node = int(input())
delete_nodes = set()
delete_nodes.add(delete_node)

delete_dfs(graph,delete_node)

# graph에서 지워질 노드들 제거
for i in range(n):
    if i in delete_nodes:
        graph[i] = []
    else:
        for j in delete_nodes:
            if j in graph[i]:
                graph[i].remove(j)


# 그래프의 리프노드 개수 구하기
global answer
answer = 0

def dfs(graph,node):
    global answer
    if graph[node]:
        for i in graph[node]:
            dfs(graph,i)
    else:
        answer += 1

if delete_node != root_node:
    dfs(graph,root_node)

print(answer)

 

 

다른 풀이

import sys
input = sys.stdin.readline

def dfs(num, arr):
    arr[num] = -2
    for i in range(len(arr)):
        if num == arr[i]:
            dfs(i, arr)

n = int(input())
arr = list(map(int, input().split()))
k = int(input())
count = 0

dfs(k, arr)
count = 0
for i in range(len(arr)):
    if arr[i] != -2 and i not in arr:
        count += 1
print(count)

 

다른 사람의 풀이이다.

내 코드와 달리 매우 짧다.

따로 그래프 배열을 선언할 필요 없이, dfs를 돌며 지워질 노드를 -2와 같이 의미 없는 수로 선언하고

해당 노드를 부모로 가지는 노드를 찾아 dfs 재귀를 돌리는 간단한 방법으로 풀 수 있었다.

다들 천재같다 진짜..