[BOJ] 11725 : 트리의 부모 찾기
🔒 예제
>> 7
>> 1 6
>> 6 3
>> 3 5
>> 4 1
>> 2 4
>> 4 7
4
6
1
3
1
4
>> 12
>> 1 2
>> 1 3
>> 2 4
>> 3 5
>> 3 6
>> 4 7
>> 4 8
>> 5 9
>> 5 10
>> 6 11
>> 6 12
1
1
2
3
3
4
4
5
5
6
6
🔧 풀이
1. 부모-자식 관계가 아닌 간선 정보 제공 -> 무방향 그래프로 입력 저장
2. 시작점(트리의 루트)가 제공 -> 그래프 탐색을 이용하여 부모 찾기
2.1 bfs(너비우선탐색) : 큐 활용
2.2 dfs(깊이우선탐색) : 스택/재귀함수를 활용
🔑 답안
import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
graph = [[] for _ in range(n + 1)]
parent = [0 for _ in range(n + 1)]
for _ in range(n - 1):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
def bfs():
q = deque()
# 루트 설정
q.append(1)
# 그래프 팀색
while q:
node = q.popleft()
for i in graph[node]:
# 큐에 넣으려는 노드들 중 해당 노드가 부모가 없으면 부모 설정
if parent[i] == 0:
parent[i] = node
q.append(i)
return parent
bfs()
for i in parent[2:]:
print(i)
💡 개념
### 너비우선탐색(bfs)
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
v = queue.popleft()
print(v, end=' ')
for i in graph[v]:
if not visited[i]:
queue.append(i)
visited[i] = True
Author And Source
이 문제에 관하여([BOJ] 11725 : 트리의 부모 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ohhj1999/BOJ-11725-트리의-부모-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)