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

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

https://www.acmicpc.net/problem/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])

from http://hidemasa.tistory.com/102 by ccl(A) rewrite - 2021-09-11 21:00:41