11725번 트리의 부모 찾기

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

---

아이디어

DFS, BFS로 문제를 풀 수 있다.

DFS

현재 노드에서 연결된 노드들을 탐색하고 방문하지 않은 노드(visited[i] == 0)를 찾으면 visited[i]에 부모 노드를 저장한다. 그 후 dfs(i)를 호출하여 그 노드와 연결된 노드들을 탐색한다.
루트 노드인 1번 노드부터 시작하기 때문에 순차적으로 저장할 수 있다. (트리 끝까지 들어갔다가 나옴)

BFS

큐에 노드를 넣어서 탐색을 한다. 큐에서 pop을 하며 해당 노드와 연결된 자식 노드를 싹 방문하고 방문하지 않은 노드면 visited[i]에 부모 노드를 저장하고 큐에 추가한다.

+) 파이썬의 최대 재귀 깊이를 설정하는 Recursion Limit을 안해주면 메모리초과가 나온다.

---

코드

DFS 버전

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

def dfs(node):
    for i in tree[node]:
        if visited[i] == 0: # 방문X
            visited[i] = node
            dfs(i)
            
n = int(input())
# root는 1
tree = [[] for _ in range(n+1)]
visited = [0]*(n+1)
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
dfs(1)
for i in range(2, n+1):
    print(visited[i])

BFS 버전

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def bfs():
    queue = deque([1])
    while queue:
        x = queue.popleft()
        for i in tree[x]:
            if visited[i] == 0:
                visited[i] = x
                queue.append(i)
    return

n = int(input())
# root는 1
tree = [[] for _ in range(n+1)]
visited = [0]*(n+1)
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)
bfs()
for i in range(2, n+1):
    print(visited[i])

함수 부분만 달라졌다.