트리_BOJ #11725: 트리의 부모 찾기

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

 

 

---

각 노드의 부모 노드 번호를 출력해야 하는 문제이다.

예제 입력 1의 트리 그래프는 다음과 같다.

노드가 7개이므로 트리 구조를 담을 graph 리스트를 다음과 같이 만든다.

graph = [ [], [], [], [], [], [], [], [] ]

첫번째 노드가 1이므로 idx가 0번째인 노드는 빈 리스트로 유지하기 위해 n+1개의 []를 만든다.

 

visited = [ 0, 0, 0, 0, 0, 0, 0, 0 ] 는 부모 노드를 입력하는 리스트이다.

visited에 값이 0 이라면(즉, 처음 방문하는 것이라면) 현재 확인하는 노드가 부모 노드이다.

 

그래프 탐색 이론중 DFS, BFS는 알고리즘상 가장 최근에 탐색한 노드의 인접한 노드를 우선적으로 탐색하는데, 이 특성을 고려하면 특정 노드가 어떤 노드에 의해 탐색이 결정되었는지 알 수 있다. 

 

루트에서 리프까지 깊이가 깊어질 수 있다는 부분을 고려하면 재귀를 이용한 DFS 풀이는 BFS 풀이보다 메모리 측면이나 시간측면에서 불리하다.

 

 

dfs 풀이

import sys
sys.setrecursionlimit(10**9)
def input():
  return sys.stdin.readline().rstrip()

# 노드의 개수
n = int(input())

# 트리
graph = [[] for i in range(n+1)]
# 부모 노드 정보 저장 리스트
visited = [0]*(n+1)

# 트리 구조 입력
for i in range(n-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

# 깊이 우선 탐색 방식
def dfs(s):
  for i in graph[s]:
    if visited[i] == 0:
      visited[i] = s
      dfs(i)

dfs(1)
for i in range(2, n+1):
  print(visited[i])

 

bfs 풀이

from collections import deque
import sys
def input():
  return sys.stdin.readline().rstrip()

# 노드의 개수
n = int(input())

# 트리
graph = [[] for i in range(n+1)]
# 부모 노드 정보 저장 리스트
visited = [0]*(n+1)

# 트리 구조 입력
for i in range(n-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

# 넓이 우선 탐색 방식
def bfs(s):
  queue = deque()
  queue.append(s)

  while queue:
    v = queue.popleft()
    for i in graph[v]:
      if visited[i] == 0:
        visited[i] = v
        queue.append(i)

bfs(1)
for i in range(2, n+1):
  print(visited[i])