https://www.acmicpc.net/step/23

백준 사이트에서는 트리 문제로 분류되어 있지만 BFS를 활용해서 풀 수 있는 문제였다.

나는 틀렸다.

입력값에서 바로 부모를 정의해줄 수가 없어서 무바향 그래프로 표현하는 것 부터 시작한다.

여기까지는 했는데, 그 다음부터 어떻게 각 노드의 부모를 정의해줘야 할 지 감이 안잡혀서 못풀었다.

내가 아는 트리는 양방향 연결리스트로 되어 있는 트리인데 여기서는 한 노드에 자식이 몇개라도 올 수 있기 때문에

어떻게 표현해줘야 할지 몰랐다.

여기서는 연결리스트 트리처럼 부모 자식 관계를 표현해줄 필요는 없고, 1번 노드를 루트로 하여 각 노드가 어떤 노드로부터 분기 되었는지에 대한 정보만 있으면 되는 거였다.

여기서는 각 노드의 이전 탐색값이 어떤 거였는지만 알면 되므로 bfs로 풀면 되었다.

1번노드부터 시작한다.