[BOJ] 11725. 트리의 부모 찾기 (Python)

11725번: 트리의 부모 찾기

 

트리의 부모 찾기 문제!

방법은 간단하다.

 

먼저 각 트리에게 연결 된 노드들의 정보를 저장한다.

루트 노드는 무조건 1번 노드로 정해져있으니 1번노드를 시작으로 DFS 또는 BFS로 순회를 하면 각 노드의 부모 노드를 한 번에 찾을 수 있다.

 

* DFS의 경우 recursion limit을 설정해두어야 한다.

 

 

<DFS 코드>

 

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
tree = [[] for _ in range(n+1)]
parents = [0 for _ in range(n+1)]
parents[1] = 1

for _ in range(n-1) :
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

def dfs(start) :
    for node in tree[start] :
        if parents[node] == 0 : # 아직 방문 전이면
            parents[node] = start # 부모 노드 설정
            dfs(node)

dfs(1)

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

 

 

<BFS 코드>

 

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
tree = [[] for _ in range(n+1)]
parents = [0 for _ in range(n+1)]
parents[1] = 1

for _ in range(n-1) :
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

def bfs() :
    q = deque([])
    q.append(1)
    while q :
        start = q.popleft()
        for node in tree[start] :
            if parents[node] == 0 :
                parents[node] = start
                q.append(node)

bfs()

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

 

 

 

위 : bfs, 밑 : dfs