Note
DFS를 활용하여 트리에서 각 노드의 부모를 찾는 문제입니다.
문제 링크
문제 요약
루트 없는 트리가 주어집니다. 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하세요.
- 입력: 노드의 개수 N과 N-1개의 간선 정보
- 출력: 2번 노드부터 N번 노드까지의 부모 노드 번호를 순서대로 출력
핵심 아이디어
트리에서의 DFS
트리는 사이클이 없는 그래프이므로, DFS를 사용하여 각 노드의 부모를 찾을 수 있습니다.
- 루트 노드(1)에서 DFS 시작
- 각 노드를 방문할 때, 그 노드의 부모를 저장
- 인접한 노드 중 부모가 아닌 노드만 탐색
부모-자식 관계
트리에서:
- 각 노드는 정확히 하나의 부모를 가짐 (루트 제외)
- DFS 탐색 시, 현재 노드가 다음 노드의 부모가 됨
- 이미 방문한 노드는 부모 노드이므로 다시 방문하지 않음
알고리즘 설계
1. 그래프 구성
graph = [[] for _ in range(n + 1)]
for _ in range(n-1):
start, end = map(int, readline().split())
graph[start].append(end)
graph[end].append(start)- 양방향 그래프로 구성 (트리는 무방향 그래프)
2. DFS 탐색
def dfs(graph, start, visited):
stack = [start]
while stack:
v = stack.pop()
if not visited[v]:
visited[v] = True
for i in graph[v]:
if not visited[i]:
nodes[i].parent = v # 부모 설정
stack.append(i)3. 부모 출력
for i in range(2, n+1):
print(nodes[i].parent)전체 코드
import sys
readline = sys.stdin.readline
class Node:
def __init__(self, value):
self.value = value
self.childrens = []
self.parent = None
self.is_root = False
def __repr__(self):
return f"\nNode({self.value}, p: {self.parent}, c: {self.childrens})"
n = int(readline().rstrip())
# dfs 하면 좋을 듯.
graph = [[] for _ in range(n + 1)]
nodes = [Node(i) for i in range(n + 1)]
nodes[1].is_root = True
visited = [False for _ in range(n + 1)]
s = []
for _ in range(n-1):
start, end = map(int, readline().rstrip().split())
graph[start].append(end)
graph[end].append(start)
def dfs(graph, start, visited):
stack = [start]
while stack:
v = stack.pop()
if not visited[v]:
visited[v] = True
for i in graph[v]:
if not visited[i]:
nodes[v].childrens.append(i)
nodes[i].parent = v
stack.append(i)
dfs(graph, 1, visited)
for i in range(2, n+1):
print(nodes[i].parent)코드 설명
1. Node 클래스
class Node:
def __init__(self, value):
self.value = value
self.childrens = []
self.parent = None
self.is_root = False- 각 노드의 정보를 저장하는 클래스
childrens: 자식 노드들parent: 부모 노드is_root: 루트 노드 여부
2. 그래프 구성
graph = [[] for _ in range(n + 1)]
nodes = [Node(i) for i in range(n + 1)]
for _ in range(n-1):
start, end = map(int, readline().split())
graph[start].append(end)
graph[end].append(start)- 인접 리스트로 그래프 구성
- 양방향 그래프 (트리는 무방향)
- 각 노드에 대한 Node 객체 생성
3. DFS 탐색
def dfs(graph, start, visited):
stack = [start]
while stack:
v = stack.pop()
if not visited[v]:
visited[v] = True
for i in graph[v]:
if not visited[i]:
nodes[v].childrens.append(i)
nodes[i].parent = v
stack.append(i)- 스택을 사용한 반복적 DFS 구현
- 현재 노드
v를 방문 처리 - 인접한 노드
i중 방문하지 않은 노드:v의 자식으로i추가i의 부모를v로 설정- 스택에 추가하여 다음에 탐색
4. 부모 출력
for i in range(2, n+1):
print(nodes[i].parent)- 2번 노드부터 N번 노드까지의 부모 출력
- 루트 노드(1)는 부모가 없으므로 제외
시간 복잡도
-
시간 복잡도: O(N)
- 모든 노드를 한 번씩 방문
- 각 노드에서 인접한 노드 확인: 총 간선 수만큼 (N-1)
-
공간 복잡도: O(N)
- 그래프: O(N)
- 노드 배열: O(N)
- 방문 배열: O(N)
- 스택: 최악의 경우 O(N)
풀이 포인트
1. 스택 기반 DFS
재귀 대신 스택을 사용한 반복적 구현:
- 스택 오버플로우 위험 없음
- 큰 트리에서도 안전하게 동작
2. 부모-자식 관계 설정
DFS 탐색 중 부모-자식 관계를 설정:
- 현재 노드
v가 다음 노드i의 부모 nodes[i].parent = v로 부모 설정nodes[v].childrens.append(i)로 자식 추가
3. 방문 체크
이미 방문한 노드는 부모 노드이므로 다시 방문하지 않음:
- 트리는 사이클이 없으므로, 방문한 노드를 다시 방문할 일이 없음
- 단, 부모 노드는 제외해야 하므로
visited배열로 체크
개선된 코드
더 간단한 구현:
import sys
from collections import deque
readline = sys.stdin.readline
n = int(readline())
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, readline().split())
graph[a].append(b)
graph[b].append(a)
parent = [0] * (n + 1)
visited = [False] * (n + 1)
def dfs(v):
visited[v] = True
for neighbor in graph[v]:
if not visited[neighbor]:
parent[neighbor] = v
dfs(neighbor)
dfs(1)
for i in range(2, n + 1):
print(parent[i])장점:
- 더 간단하고 직관적
- 재귀 호출 사용 (트리 깊이가 크지 않으면 안전)
- 별도의 Node 클래스 불필요
관련 문제
- DFS (깊이 우선 탐색) - 트리 탐색 이론
- BOJ 1260: DFS와 BFS - DFS와 BFS 기본 문제