문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
예제
DFS, BFS란?
| DFS (Depth-First Search) | BFS (Breadth-First Search) | |
| 탐색 방식 | 깊이 우선 탐색 | 너비 우선 탐색 |
| 경로 탐색 | 깊은 곳까지 탐색 후 백트래킹 (뒤로가기) | 가까운 노드부터 차례로 탐색 |
| 구현 방식 | 스택(Stack) or 재귀(Recursion) | 큐(Queue) |
| 메모리 사용 | 낮음 (경로 저장 필요 없음) | 높음 (경로 저장 필요) |
| 사용 예시 | 백트래킹 문제, 미로 찾기, 순열/조합 | 최단 거리 탐색, 네트워크 문제 |
풀이1 (DFS - 재귀)
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N+1)]
for i in range(N-1):
A, B = map(int, input().split())
graph[A].append(B)
graph[B].append(A)
visited = [0]*(N+1)
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])- 루트 노드인 `1`부터 시작해서 경로를 따라 트리 깊숙이 들어간다. DFS는 항상 부모 노드에서 자식 노드로 이동한다는 점이 이 풀이의 핵심이다.
- `visited[i] == 0`이라면, 즉 해당 노드에 처음 방문하는 것이라면 `s`라는 부모 노드를 통해 방문한 것이 되므로 `visited[i] = s`로 교체한다.
풀이2 (DFS - 스택)
import sys
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N+1)]
for i in range(N-1):
A, B = map(int, input().split())
graph[A].append(B)
graph[B].append(A)
visited = [0]*(N+1)
def dfs(node):
stack = [node]
while stack:
top = stack.pop()
for i in graph[top]:
if visited[i] == 0:
visited[i] = top
stack.append(i)
dfs(1)
for i in range(2, N+1):
print(visited[i])- `1`부터 시작해서 스택에 노드를 삽입, 삭제하면서 하나씩 내려가면서 탐색한다.
풀이3 (BFS - 큐)
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
graph = [[] for _ in range(N+1)]
for i in range(N-1):
A, B = map(int, input().split())
graph[A].append(B)
graph[B].append(A)
visited = [0]*(N+1)
def bfs(start):
queue = deque([start])
while queue:
node = queue.popleft()
for i in graph[node]:
if visited[i] == 0:
visited[i] = node
queue.append(i)
bfs(1)
for i in range(2, N+1):
print(visited[i])- 큐에서 `popleft()`로 노드를 가져오게 되면 트리 구조의 상단에 위치한 노드부터 탐색하게 되면서 BFS가 실행된다.
회고
- 처음 DFS, BFS로 풀어본 문제라 개념과 풀이 방법을 이해하는데 시간이 걸렸다.
- 처음부터 너무 완벽하게 모든 것을 이해하려고 하지 말고 알고리즘마다 어떤 구현 방식을 사용하는지, 그리고 그 구현 방식의 흐름을 파악하기 위해 노력했다.
참고