BOJ 백준 11725: 트리의 부모 찾기

Table of contents

들어가며

이 문제는 BFS를 돌리면서 각 노드를 방문하고, 각 노드에 대해 직전에 방문했던 노드를 기록해주는 리스트를 만들어서 기록해주어서 푸는 문제이다.

풀이 과정

AC 받은 Python 코드

import sys
from collections import deque

input = sys.stdin.readline


if __name__ == "__main__":
    N = int(input().rstrip())
    graph = [[] for _ in range(N + 1)]
    isVisited = [False for _ in range(N + 1)]
    pre = [0 for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v = map(int, input().rstrip().split())
        graph[u].append(v)
        graph[v].append(u)
    q = deque()
    isVisited[1] = True
    q.append(1)
    while q:
        cur = q.popleft()
        for nv in graph[cur]:
            if isVisited[nv]:
                continue
            isVisited[nv] = True
            pre[nv] = cur
            q.append(nv)
    for i in range(2, N + 1):
        print(pre[i])