TREE 관련 문제

먼저, BINARY TREE에 대한 개념을 잡고 가자. 

 

비선형의 자료구조로써. 

ROOT -> 단말노드 등의 구조를 가진다.

왼쪽의 값보다는 부모의 값이 크고, 오른쪽보단 부모의 값이 작다.

 

자료구조의 형태는 이해했으나, 이를 어떻게 활용하는지,

import heapq, heapq.heappush(array,50)혹은 heappop처럼 활용하는지 보도록 하자!

 

백준 11725

import sys

sys.setrecursionlimit(1000000)

N = int(sys.stdin.readline())

Nlist =[[] for _ in range(N+1)]

for i in range(N-1):

    a,b=list(map(int,sys.stdin.readline().split()))

    Nlist[a].append(b)

    Nlist[b].append(a)

visited = [0] * (N+1)

#0이 안방문한거

def DFS(startindex) :

    for i in Nlist[startindex]:

        if visited[i] == 0 :

            visited[i] = startindex

            DFS(i)

DFS(1)

for i in range(2,len(visited)) :

    print(visited[i])

   

 

#트리 관련 문제가 있을땐, (일단, 복잡도가 현재 100000 정도였다) DFS를 생각하자.

 

DFS가 기억이 나지 않아서 어려웠다. 

 

DFS의 구조를 기억하자.

1. 인접행렬 OR 인접리스트

2. VISITED로. 방문 확인

3. DEF DFS로 문제 풀이 (방문 노드 표시는 호출 후 하든, 호출 전 하든 일관성있게만)

4. 그 과정에서, 전의 정보를 기억하려면 VISITED에 추가하는 경우도 있고, 아닌 경우도 있다. 

 

트리의 단말은, 결국 본인을 누가 호출했냐로 귀결되기 때문에, 해당 정보를 VISITED에 저장하여 마무리하였다.