[백준/BOJ/알고리즘/파이썬(python)]#11725_트리의 부모 찾기[트리/그래프]

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

11725번: 트리의 부모 찾기

 

루트 1부터 시작해서 dfs로 탐색하는 알고리즘으로 풀었다.

방문유무 정보 저장하는 배열을 하나 만들고 방문하지 않았다면 부모노드를 업뎃하면서 dfs탐색하면 된다. 

 

재귀로 한 번 풀고 큐로 한 번 풀었다.

 

파이썬 코드_재귀 풀이(recursion)

#11725_recursion
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N = int(input())

tree = [[] for _ in range(N+1)]

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

def dfs(child,tree,parent):
    for i in tree[child]:
        if parent[i]==0: #unvisited
            parent[i]=child #parent update 
            dfs(i, tree, parent)

dfs(1, tree, parent)

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

 

 

파이썬 코드_큐 풀이(queue)

#11725_queue
import sys
from collections import deque
input = sys.stdin.readline

N = int(input())

tree= [[] for _ in range(N+1)]

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

parent = [0 for _ in range(N+1)]#visited
queue=[1]#start from root

while queue:
    child = queue.pop(0)
    for i in tree[child]:
        if parent[i]==0:
            parent[i]=child #update parent
            queue.append(i)

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