[파이썬] 백준 11725 트리의 부모찾기 ( BFS, DFS 3가지 풀이 비교)

혼자 남겨진 귀여운 트리

트리의 부모를 찾아주자.

노드(1~N)와 노드들과 연결된 간선들이 주어짐. 이때 1번 노드를 root이라고 할 때, 각 노드의 부모노드를 매칭하는 문제

문제 풀이 포인트

• 그래프 탐색 이론중 DFS, BFS는 알고리즘상 가장 최근에 탐색한 노드의 인접한 노드를 우선적으로 탐색하는데, 이 특성을 고려하면 특정 노드가 어떤 노드에 의해 탐색이 결정되었는지 알 수 있다. 
• 루트에서 시작하여 BFS 혹은 DFS를 이용하여 탐색을 시작해보자. 새로운 노드가 탐색리스트에 추가 될 때마다, 그 노드가 어떤 노드에 의해 탐색 리스트에 추가되었는지 살펴보자.

이 문제의 경우 노드의 개수가 최대 100,000개까지 가능하다, 루트에서 리프까지 깊이가 깊어질 수 있다는 부분을 고려하면 재귀를 이용한 DFS 풀이는 조금 불리할 것으로 추측했다. (그래도 이 문제는 잘풀림)

BFS, DFS 두가지 방법으로 풀어보았으며 결과는 메모리, 시간관점 모두 BFS가 유리함을 확인할 수 있었다.

 

사용 코드별 결과

시간 :  BFS < DFS(with stack) < DFS(with recursion)

메모리 : BFS = DFS(with stack) < DFS(with recursion)

 

1. BFS풀이 

#BFS 풀이 
from collections import deque
import sys
input=sys.stdin.readline


N=int(input())
visited=[False]*(N+1)
answer=[0]*(N+1)
E=[[] for _ in range(N+1)]
for i in range(N-1):
    S,D=map(int,input().split())
    E[S].append(D)
    E[D].append(S)


def bfs(E,v,visited):
    que=deque([v])
    visited[v]=True
    while que:
        x=que.popleft()
        for i in E[x]:
            if not visited[i]:
                answer[i]=x
                que.append(i)
                visited[i]=True
           

            
bfs(E,1,visited)

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

2. DFS 풀이 (재귀)

#DFS 풀이

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)

N=int(input())
visited=[False]*(N+1)
answer=[0]*(N+1)
E=[[] for _ in range(N+1)]
for i in range(N-1):
    S,D=map(int,input().split())
    E[S].append(D)
    E[D].append(S)


def dfs(E,v,visited):
    visited[v]=True
    for i in E[v]:
        if not visited[i]:
            answer[i]=v
            dfs(E, i, visited)
            

dfs(E,1,visited)


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

3. DFS 풀이(스택사용)

#DFS with Stack
from collections import deque
import sys
input=sys.stdin.readline


N=int(input())
visited=[False]*(N+1)
answer=[0]*(N+1)
E=[[] for _ in range(N+1)]
for i in range(N-1):
    S,D=map(int,input().split())
    E[S].append(D)
    E[D].append(S)

#DFS with Stack
def dfs(E,v,visited):
    visited[v]=True
    stack=deque([v])
    while stack:
        x=stack.pop()
        for i in E[x]:
            if not visited[i]:
                stack.append(i)
                visited[i]=True
                answer[i]=x
dfs(E,1,visited)
for i in range(2,N+1):
        print(answer[i])