백준 11725번 : 트리의 부모 찾기

<문제>

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

11725번: 트리의 부모 찾기

---

<코드>

from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6) # 반복 제한 풀기(default : 1000)

N = int(input())
graph = [[] for _ in range(N+1)]
parent = [-1] * (N+1)
for _i in range(N-1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
def dfs(start):
    for i in graph[start]:
        if parent[i] == -1:
            parent[i] = start
            dfs(i)
dfs(1)
for i in range(2, N+1):
    print(parent[i])


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

N = int(input())
graph = [[] for _ in range(N+1)]
parent = [-1] * (N+1)
for i in range(N-1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
def bfs(start):
    q = deque()
    q.append(start)
    while q:
        _node = q.popleft()
        for i in graph[_node]:
            if parent[i] == -1:
                parent[i] = _node
                q.append(i)
    return parent

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

---

<풀이>

• 1000회의 반복 제한을 풀어 주어야 dfs의 재귀에 의한 런타임 오류를 해결해야 한다.
• dfs : graph에서 특정 노드와 연결된 노드들의 parent가 지정되어 있는지의 여부에 따라 지정된 경우 dfs함수를 재귀적으로 돌지 않고, 지정되지 않은 경우 특정 노드를 부모 노드로 선정하고 dfs를 재귀적으로 돈다.
• 깊이 우선 탐색이므로 특정 노드의 부모노드가 선정된 경우 해당 노드와 연결된 노드간의 부모/자식의 관계를 파악하기 위해 재귀적으로 사용한다.
• bfs : 시간 복잡도를 줄이기 위해 먼저 deque를 사용하고 특정 노드와 연결된 모든 노드를 리스트에 추가하고 리스트에서 pop을 통해 특정 노드를 선정한다. 선정된 노드의 부모노드 선정 유무에 따라 다음으로 탐색할 노드를 추가하게 된다.
• 너비 우선 탐색으로 특정 노드와 연결된 노드들의 부모노드가 지정된 경우 다음으로 탐색할 노드에 해당 노드를 추가하지 않고 부모노드가 지정되지 않은 경우 이전에 방문하지 않은 것으로 판단하고 다음에 탐색하고자 하는 리스트에 추가한다.

---

참고 : https://github.com/Junuux/Algorithm/tree/main/Silver/11725

GitHub - Junuux/Algorithm