1068. 트리
1068번: 트리
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다
www.acmicpc.net
- 그래프 탐색
- 트리
프로그래머스 코드 챌린지를 하다가 느낀 거지만
트리 유형에 약한 것 같아서 트리 문제들만 골라 풀어보기로 했다 😢
트리는 모든 노드가 한 개 이하의 출발점, 한 개 이하의 도착점만 갖는 단방향 그래프이다.
따라서 노드의 방문 여부(visited)를 체크하지 않아도 된다는 특이점이 있다.
아이디어
Python에서는 포인터를 이용한 linked list 구조로 tree를 구현하지 않기 때문에,
실제로 node(와의 연결)을 제거하는 것보다는 제거한 노드를 탐색 범위에 넣지 않는 쪽을 선택했다.
코드
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n)]
parent = list(map(int, input().split()))
root = -1
for i in range(n):
if parent[i] == -1:
root = i
else:
graph[parent[i]].append(i)
deleted = int(input())
q = deque([root] if root != deleted else [])
count = 0
while q:
v = q.popleft()
leaf = 0
for i in graph[v]:
if i != deleted:
leaf += 1
q.append(i)
if not leaf:
count += 1
print(count)
주의할 예외 2가지
- root를 없앤 경우
- 기존에 leaf가 아니었던 노드가 새로 leaf가 된 경우
(특정 node의 유일한 leaf를 없앤 경우 이렇게 됨)
제출
