문제
알고리즘
- dfs 탐색을 통해 문제를 수행한다.
- 제거할 노드를 정의한다.
- 제거할 노드와 연결되어있는 리프 노드를 재귀함수를 통해 다시 제거할 노드를 찾는다.
- 반복문을 통해 제거할 노드가 아니고 리프 노드가 없다면 카운트한다.
코드
import sys
sys.setrecursionlimit(10 ** 6)
# dfs 탐색
def dfs(delete):
# 제거할 노드를 -2로 정의
tree[delete] = -2
# 반복문을 통해 제거할 노드의 리프노드를 확인
for i in range(n):
if delete == tree[i]:
# 제거할 리프 노드의 리프 노드를 재귀적으로 탐색
dfs(i)
n = int(sys.stdin.readline())
tree = list(map(int, sys.stdin.readline().split()))
d = int(sys.stdin.readline())
cnt = 0
# 노드를 삭제
dfs(d)
# 반복문을 통해 제거할 노드가 아니고 트리에 해당 노드의 리프 노드가 없다면 카운트
for i in range(n):
if tree[i] != -2 and i not in tree:
cnt += 1
print(cnt)
github
'CodingTest > Baekjoon' 카테고리의 다른 글
[baekjoon] 백준 1753번(파이썬): 최단경로 (0) | 2021.09.01 |
---|---|
[baekjoon] 백준 1389번(파이썬): 케빈 베이컨의 6단계 법칙 (0) | 2021.08.31 |
[baekjoon] 백준 1245번(파이썬): 농장 관리 (0) | 2021.08.29 |
[baekjoon] 백준 2823번(파이썬): 유턴 싫어 (0) | 2021.08.28 |
[baekjoon] 백준 17204번(파이썬): 죽음의 게임 (0) | 2021.08.27 |