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

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

트리의 부모 찾기 문제!

방법은 간단하다.

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

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

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

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)

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

from http://think-tech.tistory.com/20 by ccl(A) rewrite - 2021-12-11 22:26:40