[BOJ 11725] 트리의 부모 찾기

Breadth First Search

BOJ 11725번 트리의 부모 찾기

문제

구조화

• 노드의 개수 n 정의
• Edge의 개수는 n-1
• 각 노드의 부모 노드를 찾는 문제
• 주어진 조건 root node=1에 의해 연결된 다른 노드는 모두 1의 자식 노드
• 1을 Start Node로 BFS 호출
• State를 통해, 방문 여부를 확인하며 각 노드의 인덱스에 해당하는 State는 해당 노드의 부모 노드를 대입하여 구현
  • 즉, 예제를 기준으로 1번과 연결된 노드는 [6,4]
  • State에서 6과 4의 index에는 부모 노드인 1을 저장
  • 해당 형태를 반복

예제 시각화

해답

from collections import deque
import sys
input = sys.stdin.readline
m=int(input())
graph = [[] for i in range(m+1)]
state = [False for j in range(m+1)]
for i in range(m-1):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(len(graph)):
    graph[i] = sorted(graph[i])

def bfs(node):
    a=deque([node])
    ans = []
    state[node] = True
    while len(a):
        node = a.popleft()
        for nxt in graph[node]: # nxt는 node의 자식노드
            if state[nxt]==False:
                a.append(nxt) 
                state[nxt]=node # 자식노드의 State는 부모노드로 insert하여 출력
bfs(1)
for i in range(2,m+1):
    print(state[i])