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

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

DFS(recursion), DFS(stack), BFS 3가지로 구현

논리

현재 노드에 연결된 다음 노드들 중 부모 노드가 기록되지 않는 것들 탐색 탐색할 때 해당 노드의 부모 노드를 현재 노드로 기록

코드

import sys sys.setrecursionlimit(10000000) from collections import defaultdict, deque # dfs using recursion def DFS(graph, N, start): parents = defaultdict(lambda: None) parents[start] = True def _dfs(curr): # 현재 노드의 자식들 중 부모 노드가 기록되지 않은 것들 탐색 # 부모 노드 기록된 노드 <==> 방문 노드 for next in graph[curr]: if not parents[next]: parents[next] = curr # 부모 노드 기록 _dfs(next) _dfs(start) # ouptuts for i in range(2, N+1): print(parents[i]) return # dfs using stack def DFS_stack(graph, N, start): parents = defaultdict(lambda: None) parents[start] = True stack = [start] while stack: curr = stack.pop() # 현재 노드의 자식들 중 부모 노드가 기록되지 않은 것들 탐색 # 부모 노드 기록된 노드 <==> 방문 노드 for next in graph[curr]: if not parents[next]: parents[next] = curr stack.append(next) # ouptuts for i in range(2, N+1): print(parents[i]) return # bfs def BFS(graph, N, start): parents = [None] * (N+1) parents[start] = True q = deque([start]) while q: curr = q.popleft() # 현재 노드의 자식들 중 부모 노드가 기록되지 않은 것들 탐색 # 부모 노드 기록된 노드 <==> 방문 노드 for child in graph[curr]: if not parents[child]: parents[child] = curr q.append(child) # outputs for i in range(2, N+1): print(parents[i]) return # inputs N = int(sys.stdin.readline()) graph = defaultdict(list) for _ in range(N - 1): n1, n2 = list(map(int, sys.stdin.readline().split())) graph[n1].append(n2) graph[n2].append(n1) # 택 1 # DFS(graph, N, 1) # DFS_stack(graph, N, 1) # BFS(graph, N, 1)

from http://realbro.tistory.com/9 by ccl(A) rewrite - 2021-08-24 20:26:10