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

문제 링크

11725번: 트리의 부모 찾기

 

 

문제 설명

트리가 주어졌을 때 트리의 루트를 1이라고 하고 각 노드의 부모를 구하는 프로그램을 작성해야 한다.

 

문제 풀이

입력으로 주어지는 트리를 무향 그래프로 만들어주고 1번부터 bfs를 진행한다. 이 때 parent라는 배열을 미리 만들어두고 어떤 노드를 통해 방문하였는지를 저장해주면 parent배열에는 각 노드의 부모 노드가 저장이 될 것이다. 말로만 설명하면 어려우니 그림을 통해 같이 보자.

 

위는 문제에서 주어진 예시이다. 예시를 통해 그래프를 그려보면 다음과 같을 것이다.

7
1 6
6 3
3 5
4 1
2 4
4 7

루트 노드가 없는 트리를 가정하고 그렸기 때문에 위와 같은 그래프가 그려질 것이다.(다른 모양이어도 상관 없다. 간선만 올바르게 있으면 된다.)

여기서 1이 루트노드라고 가정하고 1번부터 bfs를 진행한다. (방문 표시는 녹색으로 진행할 것이다.)

4와 6은 1을 통하여 방문했기 때문에 부모노드가 1이 된다. (이를 parent 노드에 저장한다. index=4, 6인 위치에 1을 각각 넣어준다.)

 

이후 4를 통하여 2와 7에 방문할 수 있고 2와 7의 부모노드는 4가 된다.

 

이후 6을 통하여 3에 방문할 수 있기 때문에 3의 부모 노드는 6이 된다.

 

이후 3을 통하여 5에 방문할 수 있기 때문에 5의 부모 노드는 3이 된다. 그리고 모든 노드를 방문했기 때문에 bfs는 종료된다. 그리고 parent 배열은 다음과 같을 것이다.

 

코드