난이도 : 실버 2
유형 : 트리
https://www.acmicpc.net/problem/11725

문제

노드의 개수 N 을 입력 받고
연결된 두 정점이 주어졌을 때
예제 1을 그림으로 그려보면

다음과 같은 트리가 만들어진다.

출력은 1번 노드를 제외하고 2번노드부터 N번노드까지 그 부모 노드를 출력해주면 된다.

해결 아이디어

1. 입력으로 트리의 간선 정보를 받아서 인접 리스트 형태로 그래프를 만든다.
2. parent 배열을 크기 N+1로 만들어서 부모를 기록할 준비를 한다.
3. 1번 노드부터 BFS로 돌면서 방문한 적 없는 노드라면 부모를 기록하고 탐색을 이어간다.
4. 2번 노드부터 N번 노드까지 parent[i]를 출력한다.

해답 및 풀이

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

N = int(input())
graph = [[] for _ in range(N+1)]

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

parent = [0] * (N+1) # 부모 노드 저장용 배열
visited = [False] * (N+1)

# BFS
queue = deque([1])
visited[1] = True

while queue:
    cur = queue.popleft()
    for nxt in graph[cur]:
        if not visited[nxt]:
            visited[nxt] = True
            parent[nxt] = cur # 부모 기록
            queue.append(nxt)

# 결과 출력

for i in range(2, N+1):
    print(parent[i])