11725번: 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

 

입력으로 주어지는 것들이, '처음에 나오는 것이 부모다'라는 말이 없어서 undirectional graph로 트리를 생성했다.

노드 1이 항상 루트이므로, 노드 1에서부터 BFS를 수행하며 노드의 부모를 찾는 것을 목표로 했다.

 

# https://www.acmicpc.net/problem/11725
# Tree, BFS

import sys
from collections import defaultdict, deque

N = int(input())

tree = defaultdict(list)
for _ in range(N-1) :
    a, b = map(int, sys.stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)

visited = [0] * (N+1)

def BFS() :
    q = deque([1])
    visited[1] = 1

    while q :
        e = q.popleft()

        for v in tree[e] :
            if visited[v] == 0 :
                visited[v] = e
                q.append(v)
                
    for node in range(2, N+1) :
        print(visited[node])

BFS()

 

1번 노드는 visited 0번이 아니라 1번에, 2번 노드는 visited의 2번에 기록하도록 N+1의 길이를 가진 배열을 생성한다.

 

for문에서, BFS 탐색을 시도하는데, visited가 0이라면, visited에 현재 노드 정보를 입력하여 부모 노드가 누군지 기록한다.

이후 BFS를 완료하고 visited의 2번째부터 출력하도록 한다.