[백준/1068] 트리

1068 트리

1068번: 트리

 

 

---

알고리즘

1. 이 문제는 부모가 인덱스, 해당 인덱스의 자식을 리스트로 부여한다.

아래와 같이 이차원 리스트에 부모[i] = 자식을 표현할 수 있다!

 

# index: 부모, 값: 자식
# 노드의 범위가 0 ~ n-1인 경우
for i in range(n):
    # root인 경우
    if tree[i] == -1 : 
        continue
    else:
        graph[tree[i]].append(i)

 

이렇게 표현하는 이유는 DFS 탐색 구현을 좀 더 직관적으로 평소와 같이 할 수 있기 때문이다. 예컨대 dfs(i)로 시작해서 자식 → 자식 → … 으로 나아가는 방향을 말한다.

 

 

 

2. 노드가 K부터 잘렸다…를 표현하기가 어려워서 리프노드의 정의를 활용하였다.

• 리프노드란 자식이 없는 노드이므로, 이차원 리스트로 부모/자식을 표현했을 때 리스트가 비어있을 것이다. 따라서 100이라는 임의의 값을 넣음으로써 리프노드로 인식하지 않도록 하였다. 그런데 이 문제가 단순히 리프노드의 개수를 세는 문제였기 때문에 이 알고리즘이 가능하다.

 

 

3. 주의할 점은 루트노드다. 모든 노드가 잘리고 루트 노드만 남았다면 이 또한 리프노드이기 때문에 카운팅을 할 때 아래와 같은 조건식을 추가하였다.

for i in graph:
    if k in i and len(i) == 1 :
        cnt += 1
    if len(i) == 0 :
        cnt += 1

 

---

전체 코드

import sys;input=sys.stdin.readline

n=int(input())
tree=list(map(int,input().split()))
k=int(input())

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

# index: 부모, 값: 자식
for i in range(n):
    # root인 경우
    if tree[i] == -1 : 
        continue
    else:
        graph[tree[i]].append(i)

def dfs(x):
    visited[x] = True
    
    for i in graph[x]:
        if not visited[i]:
            dfs(i)
            graph[i].append(100)
    graph[x].append(100)

dfs(k)
cnt=0
for i in graph:
    if k in i and len(i) == 1 :
        cnt += 1
    if len(i) == 0 :
        cnt += 1

print(cnt)

 

---

알게된 점

• 트리 > 그래프 > DFS 떠올려보기
• 2차원 리스트로 부모/자식 그래프 표현하기
• 자료구조의 정의는 까먹지 않도록 평소에 주의하자