Jinho Tech

트리 & DFS & BFS 문제이다. 시간 초과를 매우 조심해야 되는 문제다. 처음에 방문 체크 리스트를 N-2번 생성하고 순서대로 체크하도록 구현했어서 그런지 시간 초과가 엄청 나왔다.

DFS 풀이

import sys
sys.setrecursionlimit(300000)

def dfs(node):
    for n in graph[node]:
        if p[n] == 0:
            p[n] = node
            dfs(n)

N = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
p = [0]*(N+1)
dfs(1)
for i in range(2, N+1):
    print(p[i])

BFS 풀이

import sys
from collections import deque

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        for n in graph[node]:
            if p[n] == 0:
                p[n] = node
                queue.append(n)

N = int(sys.stdin.readline())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
p = [0]*(N+1)
bfs(1)
for i in range(2, N+1):
    print(p[i])