[백준 - Python] 11725. 트리의 부모 찾기 (DFS/BFS)

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

11725번: 트리의 부모 찾기

 

코드

import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())

graph = [[] for i in range(n+1)]

for i in range(n-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [0] * (n+1)

def dfs(s):
    for i in graph[s]:
        if visited[i] == 0:
            visited[i] = s
            dfs(i)
    
dfs(1)

for x in range(2, n+1):
    print(visited[x])

 

트리의 루트가 1이므로 1번 노드부터 탐색을 시작한다.

 

1번 노드와 연결되어 있는 노드들 중,

방문하지 않은 노드를 방문하는데,

방문 후에는 visited 배열에 탐색을 시작한 노드 번호를 저장해

0이 아닌 경우로 만들어 방문 처리를 한다.

 

visited 배열을 방문 여부를 판단하는데에만 쓰는 것이 아니라

정보를 저장하는 변수로 사용할 수 있음을 배웠다.