728x90
반응형
풀기 전 생각해보기😮
- 가급적 pypy3로 채점할 것을 추천한다 - python3로 채점이 정말 오래 걸렸다
- 트리 구조를 그리고, 각 노드의 부모를 찾는 문제
- DFS로 풀 경우 recursionlimit을 10**6까지는 열어둬야 한다
풀이🛫
BFS 풀이
from collections import deque
def bfs(node):
queue = deque()
queue.append(node)
while queue:
n = queue.popleft()
for i in graph[n]:
if parent[i] == -1:
parent[i] = n
queue.append(i)
N = int(input())
graph = [[] for _ in range(N+1)]
parent = [-1 for _ in range(N+1)]
for _ in range(N-1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
bfs(1)
for i in range(2, N+1):
print(parent[i])
DFS 풀이
import sys
sys.setrecursionlimit(10**6)
def find(node):
for n in graph[node]:
if parent[n] == -1:
parent[n] = node
find(n)
N = int(input())
graph = [[] for _ in range(N+1)]
parent = [-1 for _ in range(N+1)]
for _ in range(N-1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
find(1)
for i in range(2, N+1):
print(parent[i])
핵심 정리🎁
- for문으로 각 노드를 탐색을 시도한다
- 노드에 방문정보가 없을 때(parent == -1), 부모 노드 값을 입력한다
링크💎
https://www.acmicpc.net/problem/11725
후기 😎
- 트리 기본 문제
'Algorithm Study > Python' 카테고리의 다른 글
[백준 파이썬] #11003. 최솟값 찾기 (0) | 2023.03.22 |
---|---|
[백준 파이썬] #1967. 트리의 지름 (0) | 2022.12.27 |
[백준 파이썬] #2644. 촌수계산 (0) | 2022.12.26 |
[백준 파이썬] #2206. 벽 부수고 이동하기 (1) | 2022.12.20 |
[백준 파이썬] #2638. 치즈 (0) | 2022.12.19 |