BaekJoon 11725번 : 트리의 부모 찾기 (python)

BaekJoon 11725번 : 트리의 부모 찾기 (S2 42.454%)

트리의 부모 찾기 문제

BFS를 통한 트리의 부모 노드를 찾는 문제이다.

• 노드들을 양방향으로 입력받아 추가해주고 bfs를 통한 탐색을 한다.
• 만약 bfs를 통해 루트 노드인 1부터 탐색했을 때 만약 해당 원소의 반복문에서 발견된 값들은 해당 원소를 부모 노드로 가지는 하위 노드들이라는 것을 알 수 있다.
• 그렇게 해당 노드들의 값을 부모 노드로 넣어주고 방문 여부를 체크해주며 불필요한 방문을 하지 않게 된다.

import sys
from collections import deque
input = sys.stdin.readline

def bfs(n) :
    q = deque()
    q.append(1)
    check = [False]*(n+1)
    check[1] = True
    while q :
        x = q.popleft()
        for i in maps[x] :
            if not check[i] and result[i] == 0 :
                result[i] = x
                check[i] = True
                q.append(i)
n = int(input())
maps = [[] for _ in range(n+1)]
result = [0]*(n+1)
for _ in range(n-1) :
    a, b = map(int,input().split())
    maps[a].append(b)
    maps[b].append(a)
bfs(n)
for i in range(2, n+1) :
    print(result[i])