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

🥚문제

---

🥚입력/출력

---

🍳코드

1. BFS를 이용한 코드

import sys
from collections import deque
input = sys.stdin.readline

n = int(input().strip())

# 인접리스트
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

# bfs
def bfs(start, visited, parent):
    q = deque([])
    q.append(start)
    visited[start] = True

    while q:
        v = q.popleft()
        for w in graph[v]:
            if not visited[w]:
                q.append(w)
                visited[w] = True
                parent[w] = v

# parent[x] = 노드x의 부모노드
parent = [0]*(n+1)
# 방문표시
visited = [False]*(n+1)
# bfs 실행
bfs(1, visited, parent)
# 출력
for i in range(2, n+1):
    print(parent[i])

2. DFS를 이용한 코드

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

n = int(input().strip())

# 인접리스트
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

# dfs
def dfs(start, visited, parent):
    for v in graph[start]:
        if not visited[v]:
            visited[v] = True
            parent[v] = start
            dfs(v, visited, parent)


parent = [0]*(n+1)
visited = [False]*(n+1)
dfs(1, visited, parent)
for i in range(2, n+1):
    print(parent[i])

---

🧂아이디어

탐색

• BFS, DFS를 이용하여 풀이하는 기본적인 문제
• DFS 이용 시 주의사항
  • recursionlimit을 조정해줘야함. BOJ 채점 서버에서는 recursion limit이 1,000으로 설정되어 있는데, 이 값을 수정해야 Recursion Error가 나지 않는다