[백준 파이썬] #11725. 트리의 부모 찾기

풀기 전 생각해보기😮

• 가급적 pypy3로 채점할 것을 추천한다 - python3로 채점이 정말 오래 걸렸다
• 트리 구조를 그리고, 각 노드의 부모를 찾는 문제
• DFS로 풀 경우 recursionlimit을 10**6까지는 열어둬야 한다

---

풀이🛫

BFS 풀이

from collections import deque

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        n = queue.popleft()
        for i in graph[n]:
            if parent[i] == -1:
                parent[i] = n
                queue.append(i)


N = int(input())
graph = [[] for _ in range(N+1)]
parent = [-1 for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

bfs(1)

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

DFS 풀이

 

import sys
sys.setrecursionlimit(10**6)

def find(node):
    for n in graph[node]:
        if parent[n] == -1:
            parent[n] = node
            find(n)

N = int(input())
graph = [[] for _ in range(N+1)]
parent = [-1 for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

find(1)

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

 

핵심 정리🎁

• for문으로 각 노드를 탐색을 시도한다
• 노드에 방문정보가 없을 때(parent == -1), 부모 노드 값을 입력한다

 

링크💎

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

후기 😎

• 트리 기본 문제