게시물을 작성하면서 복습하는 문제를 선정하는 기준은<solved.ac 티어 실버 2 (Silver 2) 이상>입니다.
※ 본 사진과 해당 게시글 내용의 문제 모두 백준 : 온라인 저지[Baekjoon_OnlineJudge]사이트에서 발췌해왔습니다.
백준 온라인 저지 (Baekjoon Online Judge) :
메모리 : 54228KB
시간 : 384ms
트리 루트를 1이라고 가정 : 시작 노드
deque
를 활용해서 풀이했고
입력되는 경로에 대해
graph
를 만들어 서로 갈 수 있는 노드들 양방향에 서로를 넣어주고
popleft
되어 나오는 노드값들 마다
갈 수 있는 노드들을 조회하는 for문을 활용해서
최초로 방문하는 노드의 부모로 자신을 넣어준 후,
도착 노드값을 다시 큐에 삽입하는 형태로 풀이하였다.
마지막으로
출력조건이
2번 노드부터 순서대로 출력하는 것이기 때문에
Parent[2:]
를 사용하였다.
import sys
input = sys.stdin.readline
N = int(input())
visited = [0 for _ in range(N+1)]
graph = [[] for _ in range(N+1)]
for _ in range(N-1) :
p, c = map(int,input().split())
graph[p].append(c)
graph[c].append(p)
Parent = [i for i in range(N+1)]
root = 1
from collections import deque
q = deque([root])
visited[root] = 1
while q :
node = q.popleft()
for v in graph[node] :
if visited[v] == 0 :
q.append(v)
Parent[v] = node
visited[v] = 1
for p in Parent[2:]:
print(p)