백준 11725 트리의 부모 찾기 파이썬

링크

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

문제

DFS

DFS의 정의는 깊이우선탐색이며, ‘한 점을 기준으로 파고파고들다가, 끝점에서 다시 복귀하는 과정' 을 거친다는것이 특징이다. BFS에서는 deque()를 써서 구현하지만, DFS에서는 단순 재귀만으로 구현할수 있다.

 

sys.setrecursionlimit(10**7)

재귀방식을 사용하는 DFS의 특성은 Python에서 무한재귀로 빠질 위험이 있다.

따라서 무한재귀를 막기위해, sys.setrecursionlimit(10**7) 를 해주는 것이 일반적이다.

 

DFS(코드)

def dfs(v,graph,visit): 
    # print(v)
    visit[v] = True 
    for i in graph[v] :
        if visit[i] == False : 
            result[i] = v
            dfs(i,graph,visit)
    
dfs(1,graph,visit)

해당 노드(v)를 방문처리 하고,

연결된 노드들 중에(graph[v])

아직 방문하지않은 노드에 대해서 (visit[i] == False)

재귀를 진행한다

 

전체 소스코드

# graph = [[], [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]]
# 1 - 6 - 3 - 5
#   - 4 - 2
#       - 7

import sys 
input = sys.stdin.readline 
sys.setrecursionlimit(10**7)

N = int(input().strip())
graph = [[] for _ in range(N+1)]
for _ in range(N-1) :
    a, b = map(int ,input().split())
    graph[a].append(b)
    graph[b].append(a)

visit = [False for _ in range(N+1)]
result = [0 for _ in range(N+1)]

def dfs(v,graph,visit): 
    # print(v)
    visit[v] = True 
    for i in graph[v] :
        if visit[i] == False : 
            result[i] = v
            dfs(i,graph,visit)
    
dfs(1,graph,visit)

for i in range(2,N+1) :
    print(result[i])