[Python] 백준 11725번 트리의 부모 찾기

문제

11725번: 트리의 부모 찾기

입력

• 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

• 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

입력 예제

7
1 6
6 3
3 5
4 1
2 4
4 7

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

출력 예제

4
6
1
3
1
4

1
1
2
3
3
4
4
5
5
6
6

문제 풀이

• 루트노드가 1부터 시작하므로, 노드1에서 탐색을 시작한다.
• 부모노드는 자식노드를 방문한 노드이므로 이전에 탐색한 노드의 값을 방문리스트에 넣어 차례대로 출력한다.

BFS 코드

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
for _ in range(n - 1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

def bfs(v):
    queue = deque()
    queue.append(v)
    visited[v] = 1
    while queue:
        now = queue.popleft()
        for i in graph[now]:
            if not visited[i]:
                visited[i] = now
                queue.append(i)
bfs(1)
for i in range(2,n + 1):
    print(visited[i])

DFS 코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
for _ in range(n - 1):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    for i in graph[v]:
        if not visited[i]:
            visited[i] = v
            dfs(i)
dfs(1)
for i in range(2,n + 1):
    print(visited[i])