[백준] 11725 트리의 부모 찾기 | Sil2 | BFS,DFS Python

[백준] 11725 트리의 부모 찾기 | Sil2 | BFS,DFS Python

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

 

bfs dfs 까먹을 것 같아서 몸풀기!

세가지 방법으로 풀어보았다.

 

구상

• 풀이 1 : dfs - 재귀 (71496KB, 336ms)
  파이썬 재귀 깊이 제한을 조정하는 코드를 추가해서 통과했는데, 부하가 있는 것 같아 다른 방법도 풀어보기로
• 풀이 2 : dfs - stack (61568KB, 312ms)
• 풀이 3 : bfs - queue(deque) (62040KB, 300ms)
  
  
• 성능은 채점시마다 약간의 오차가 있는걸 감안하면, 세가지 풀이에 그렇게 큰 차이는 없는 듯 하다.
  그래도 역시 bfs가 젤 빠르게 나오긴 했다만
• 출력문으로 print말고 더 빠르다는 sys.stdout.write() 을 사용해봤다.
  print는 알아서 string 으로 바꿔주지만 write는 str()을 써서 string으로 바꿔넣어줘야 한다.

[문제 해석]

• 연결된 정점 목록 주어짐
• 답 : 루트노드를 1번노드로 정했을 때, 2번노드부터 해당 노드의 부모노드 번호를 출력

 

 

트러블 슈팅

• dfs 재귀로 구현했는데, 채점에서 Recursion error가 떴다.
  • 백준 채점 시 파이썬에는 1000번 이상의 재귀호출 시 Recursion 에러가 발생하도록 되어있는데, 이 값을 조정할 수 있다.
    sys.setrecursionlimit(100000) 이렇게
  • 이 방식으로 재귀 최댓값을 늘렸을 때, 재귀의 깊이가 채점 서버가 감당할 수 없는 정도로 깊어지면, Segmentation fault가 발생해 런타임 에러 이유로 SegFault를 받게된다고 한다.
     -> sys.setrecursionlimit(10**9) 로 늘려서 해결

 

코드 - DFS 재귀

# v1 : dfs - recursion (71496KB, 336ms)
# TS : dfs 재귀로 구현했는데, 채점에서 Recursion error가 떴다.
#       백준 채점 시 파이썬에는 1000번 이상의 재귀호출 시 Recursion 에러가 발생하도록 되어있는데, 이 값을 조정할 수 있다.
#       sys.setrecursionlimit(100000) 이렇게
#       이 방식으로 재귀 최댓값을 늘렸을 때, 재귀의 깊이가 채점 서버가 감당할 수 없는 정도로 깊어지면, Segmentation fault가 발생해 런타임 에러 이유로 SegFault를 받게된다고 한다.
#       -> sys.setrecursionlimit(10**9) 로 늘려서 해결. 부하가 있는 것 같으니 다른 방법으로도 풀어봐야겠음

'''
[문제 해석]
- 연결된 정점 목록 주어짐
답 : 루트노드를 1번노드로 정했을 때, 2번노드부터 해당 노드의 부모노드 번호를 출력
'''

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9) # TS : Recursion error 방지

N = int(input())
edge = defaultdict(list)

for _ in range(N-1) :
    n1, n2 = map(int, input().split())
    edge[n1].append(n2)
    edge[n2].append(n1)


#dfs
parent_arr = [0]*(N+1)

def dfs(cur, parent) :
    for child in edge[cur] :
        if child == parent : #부모노드는 넘어감
            continue
        parent_arr[child] = cur #해당 자식노드의 부모노드로 기록
        dfs(child, cur)

dfs(1,0) #1의 부모노드는 존재하지 않으므로 무의미한 값인 0 넣음

#출력
# print('\n'.join(map(str, parent_arr[2:]))) #아래와 같은 동작
sys.stdout.write('\n'.join(map(str, parent_arr[2:])))

 

코드 - DFS 스택

# v2 : dfs - stack (61568KB, 312ms)

'''
- 연결된 정점 목록
답 : 루트노드를 1번노드로 정했을 때, 2번노드부터 해당 노드의 부모노드 번호를 출력
'''

from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
edge = defaultdict(list)

for _ in range(N-1) :
    n1, n2 = map(int, input().split())
    edge[n1].append(n2)
    edge[n2].append(n1)


#dfs
parent_arr = [0]*(N+1)
stack = []
stack.append((1,0))

while stack :
    cur, parent = stack.pop()
    for child in edge[cur] :
        if child == parent : #부모노드는 넘어감
            continue
        parent_arr[child] = cur #해당 자식노드의 부모노드로 기록
        stack.append((child, cur)) #dfs

#출력
sys.stdout.write('\n'.join(map(str, parent_arr[2:])))

 

코드 - BFS

# v3 : bfs - queue(deque) (62040KB, 300ms)

'''
- 연결된 정점 목록
답 : 루트노드를 1번노드로 정했을 때, 2번노드부터 해당 노드의 부모노드 번호를 출력
'''

from collections import defaultdict, deque
import sys
input = sys.stdin.readline

N = int(input())
edge = defaultdict(list)

for _ in range(N-1) :
    n1, n2 = map(int, input().split())
    edge[n1].append(n2)
    edge[n2].append(n1)


#bfs
parent_arr = [0]*(N+1)
que = deque()
que.append((1,0))

while que :
    cur, parent = que.popleft()
    for child in edge[cur] :
        if child == parent : #부모노드는 넘어감
            continue
        parent_arr[child] = cur #해당 자식노드의 부모노드로 기록
        que.append((child, cur)) #bfs

#출력
sys.stdout.write('\n'.join(map(str, parent_arr[2:])))