[파이썬] BOJ_11725(트리의 부모 찾기) dfs/bfs

 

 

 

문제

 

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

11725번: 트리의 부모 찾기

---

 

해설

 

반응형

 

가장 기본적인 dfs/bfs 문제들은 visited 배열을 만들어서 방문 여부를 저장하는데

이 문제는 그 대신 부모 노드를 저장하면 된다.

그 외에는 다른 그래프 탐색 문제 풀 듯 풀면 된다.

---

코드

 

-파이썬

#백준 11725(트리의 부모 찾기)
##dfs 풀이
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

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

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]

def dfs(root):
    for next in graph[root]:
        if parents[next] == 0:  #연결된 부모 노드가 없으면
            parents[next] = root  #현재 노드를 부모 노드로 설정
            dfs(next)

dfs(1)
for i in range(2, n+1):
    print(parents[i])
    
#-----------------------------------------------------------------------------------

##bfs 풀이
#백준 11725(트리의 부모 찾기)

import sys
input = sys.stdin.readline
from collections import deque

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

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a] += [b]
    graph[b] += [a]

def bfs(root):
    Q = deque([root])
    while Q:
        current = Q.popleft()
        for next in graph[current]:
            if parents[next] == 0:
                parents[next] = current #현재 노드를 부모 노드로 설정
                Q.append(next)

bfs(1)
for i in range(2, n+1):
    print(parents[i])