[알고리즘/백준] 11725번 - 트리의 부모 찾기

11725번 트리의 부모 찾기 - https://www.acmicpc.net/problem/11725

 

 

카테고리 : Tree / BFS(그래프 탐색) 

 

접근 방법

 

노드 정보를 받을 때 트리 상에서 연결된 두 정점에 대해서 받게 된다.

따라서 정보를 받을 때 누가 부모인지 알 수 없어서 먼저 Tree를 2차원 리스트에 담아주었다.

 

노드 번호를 인덱스로 사용하기 위해 0번째 인덱스는 사용하지 않았다.

그리고 그래프처럼 각 정점에 대해 연결된 서로의 정점 정보를 모두 담아주었다.

 

node = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    n1, n2 = map(int, input().split())
    node[n1].append(n2)
    node[n2].append(n1)

 

정점 정보를 저장해 둔 리스트를 BFS로 부모 노드를 찾도록 했다.

문제에서 root node를 1로 정해주었기 때문에

1부터 각 리스트의 자식 노드로 이동하면서 부모의 정보를 p_node 리스트에 저장해두었다.

이 때 리스트에는 자식, 부모 상관없이 모두 저장되어 있기 때문에

이후 방문 시 부모도 재방문하는 경우가 생길 수 있기 때문에 

p_node 리스트에 이미 부모의 정보가 저장되어 있는 경우는 queue에 다시 넣지 않았다.

(p_node 정보를 통해 visited도 확인)

1은 맨 처음 방문하기 때문에 -1로 설정해두었다.

 

def BFS(node):
    p_node = [0] * (N + 1)
    queue = deque([1])
    p_node[1] = -1

    while queue:
        n = queue.popleft()
        for i in node[n]:
            if p_node[i] == 0:
                p_node[i] = n
                queue.append(i)

    return p_node[2:]

 

 

---

코드

 

- 최종 코드

 

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

def BFS(node):
    p_node = [0] * (N + 1)
    queue = deque([1])
    p_node[1] = -1

    while queue:
        n = queue.popleft()
        for i in node[n]:
            if p_node[i] == 0:
                p_node[i] = n
                queue.append(i)

    return p_node[2:]

N = int(input())
node = [[] for _ in range(N + 1)]


for _ in range(N - 1):
    n1, n2 = map(int, input().split())
    node[n1].append(n2)
    node[n2].append(n1)


print(*(BFS(node)), sep='\n')