백준 11725번 파이썬 문제풀이(트리의 부모 찾기)

---

간단히 dfs 나 bfs로 노드를 타고 들어가면서 그전의 노드를 부모로 설정해주는 부모를 가리키는 리스트하나만 만들면 된다. 두개 모두 코드를 올려놨다.

 

import sys
from collections import deque

sys.setrecursionlimit(5000)

input = sys.stdin.readline

def dfs(cur):
    visited[cur] = True

    for nxt in graph[cur]:
        if not visited[nxt]:
            parent[nxt] = cur
            dfs(nxt)


def bfs(start):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()

        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                parent[i] = v
                queue.append(i)


N = int(input())  # 간선의 개수는 노드개수 - 1
graph = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [False] * (N + 1)
parent = [0] * (N + 1)

bfs(1)

for i in parent[2:]:
    print(i)