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

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

11725번: 트리의 부모 찾기

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

---

문제에서 주어진 노드가 어떤 것이 부모인지 알 수 없다.

다만 확실한 것은 1번이 루트 노드라는 것이다. 그렇다면 모든 노드에 자신과 연결된 노드들의 정보를 저장한 다음 1번 노드부터 자식 노드를 찾아간다면 자식 노드와 연결된 노드 중 이미 방문한 부모 노드를 제외 한 다른 노드들은 자식 노드가 되는 것이다.

이와 같은 개념을 BFS를 활용하여 풀 수 있다.

 

---

보자마자 어떻게 풀지는 생각하지 못했지만 트리를 우선 그리고 보유한 정보로 풀어 나가려 하다보니 자연스럽게 풀었다. 난이도가 쉬운 문제인 만큼 빠르고 정확하게 풀 생각이었는데 성공적으로 달성한것 같다.