1. 문제 분석
트리가 주어지는데 루트가 없는 상태다.
루트를 1번 노드로 정한다.
각 노드의 부모를 찾아야 한다.
N-1개의 간선이 주어지므로, 트리의 기본 성질(노드 N개 → 간선 N-1개)이 성립함.
출력은 2번 노드부터 차례대로 부모 노드를 출력해야 한다.
2. 데이터 구조 정리
그래프 표현 방법
인접 리스트 (Adjacency List)를 사용한다.
트리는 양방향 그래프처럼 주어지므로, 각 노드의 연결 정보를 저장해야 함.
부모 정보를 저장할 배열
parent[i]를 만들어서 i번 노드의 부모 노드를 저장한다.
초기에는 parent 배열을 모두 0으로 두고, 나중에 갱신한다.
탐색 방법 (DFS 또는 BFS)
루트(1번 노드)에서 자식 노드들을 탐색하며 부모를 찾는다.
DFS (깊이 우선 탐색): 한 방향으로 끝까지 탐색한 후 돌아옴.
BFS (너비 우선 탐색): 가까운 노드부터 차례대로 탐색.
3. 알고리즘 설계
그래프를 인접 리스트로 저장
graph[i] = [연결된 노드들] 형태로 저장.
루트(1번 노드)에서 탐색 시작
부모를 저장할 parent 배열을 생성.
parent[1] = 0 (루트는 부모가 없음).
트리 탐색 (DFS 또는 BFS)
parent 배열을 채워나가면서 탐색 진행.
현재 방문한 노드의 연결된 노드 중 아직 부모가 없는 노드를 갱신.
결과 출력
2번 노드부터 N번 노드까지 parent[i]를 출력.
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
# 2차원 배열 생성
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
x, y = map(int, input().split())
graph[x].append(y)
graph[y].append(x)
parent = [0] * (n + 1)
def bfs():
q = deque([1])
while q:
# 현재 노드
node = q.popleft()
# 현재 노드와 연결된 모든 노드 확인
for neighbor in graph[node]:
# 부모가 정해지지 않은 경우
if parent[neighbor] == 0:
# 연결된 노드의 부모는 현재 노드
parent[neighbor] = node
q.append(neighbor)
bfs()
for i in range(2, n + 1):
print(parent[i])4. 정리
트리 성질 분석 → 간선 N-1개 → 그래프 탐색 (DFS/BFS) 필요.
입력 방식 고려 → sys.stdin.readline 사용해서 빠르게 입력.
그래프 저장 방식 결정 → 인접 리스트 사용.
탐색 방법 결정 → DFS/BFS 중 BFS 사용.
BFS 탐색하며 부모 배열 채우기.
2번 노드부터 N번 노드까지 부모 노드 출력.
