[C++] 백준 11725 - 트리의 부모 찾기

🔐 백준 11725 - 트리의 부모 찾기

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

🔑 풀이

트리가 주어지고, 루트를 1로 놓았을 때의 각 노드의 부모를 구하는 문제이다.

BFS 알고리즘을 이용하여 루트부터 트리를 탐색하는 풀이를 사용했다.

각 노드의 부모 노드를 저장하는 parent[] 배열을 만들고, 트리를 순회하면서

부모 배열을 채우는 방식으로 구현하였다.

if (parent[cur] == next) continue; 이 조건문에서 현재 노드의 부모가 이후에 확인할

노드라면 건너뛰어 주었다. 쉽게 말하면, 한 노드를 탐색할 때, 그 노드의 자식만을 확인하도록

제한한 것이다. 따라서 인접 노드인 next는 모두 cur의 자식일 것이며, parent[next] = cur;

로 부모 배열을 채워주게 된다.

🧩 코드

+