BOJ 11725 트리의 부모 찾기
7961 단어 2021.01.172021.01.17
https://www.acmicpc.net/problem/11725
시간 1초, 메모리 256MB
input :
- N (2 ≤ N ≤ 100,000)
- a b(트리 상에서 연결된 두 정점)
output :
- 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력
조건 :
- 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램
양방향 그래프를 저장하듯 인접리스트에 저장을 하자.
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
parent 1차원 리스트를 만들어서 저장을 하자.
parent는 자기자신으로 초기화를 해둠.
parent = [i for i in range(n + 1)]
해서 자기자신을 가르키지 않을 경우엔 이미 방문을 한 것.
visit 대신에도 사용할 수 있다.
import sys
from _collections import deque
n = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]
parent = [i for i in range(n + 1)]
for i in range(n - 1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
def BFS():
start = 1
q = deque([start])
while q:
now = q.popleft()
for next_node in graph[now]:
if parent[next_node] == next_node:
parent[next_node] = now
q.append(next_node)
BFS()
for i in range(2, len(parent)):
print(parent[i])
Author And Source
이 문제에 관하여(BOJ 11725 트리의 부모 찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsin2475/BOJ-11725-트리의-부모-찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)