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

백준 실버2 문제인 '트리의 부모 찾기'를 C++로 BFS를 사용해 풀어보았다.

 

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

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

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

 

트리의 루트는 무조건 1이므로, 1번 예제의 트리를 그림으로 그려보면 다음과 같다.

1번 예제 트리

코드는 다음과 같다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<vector<int>> connected(N+1);

    int newN = N-1;
    while (newN--) {
        int a, b;
        cin >> a >> b;
        connected[a].push_back(b);
        connected[b].push_back(a);
    }

    queue<int> q;
    q.push(1);
    vector<int> parents(N+1, 0);
    parents[1] = -1;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int i=0; i<connected[curr].size(); i++) {
            int next = connected[curr][i];
            if (parents[next] != 0)
                continue;
            parents[next] = curr;
            q.push(next);
        }
    }

    for (int i=2; i<=N; i++)
        cout << parents[i] << "\n";
    
    return 0;
}

(1) 2차원 벡터 connected를 만들어 서로 연결된 노드의 정보를 모두 저장했다.

(2) 1차원 벡터 parents를 만들어 parents[index]에 index의 부모 노드가 저장되도록 했다.

1의 경우 루트이므로 맨 처음에 -1로 예외처리해주었다.

처음에 queue에 1을 push한 후 BFS를 시작하게 된다.

curr는 queue의 맨 앞 원소인 1이 되고, queue에 pop을 시켜 맨 앞 원소를 제거한다.

connected[curr]에 있는 원소들을 돌며(next=6, next=4) 부모 정보가 없을 경우 (parents[next]가 0일 경우) parents[next]에 curr을 저장한다.

next를 queue에 push하고, 위 과정을 반복한다.

과정을 그림으로 나타내면 다음과 같다.

원래 vector<bool> visited를 만들어 방문했는지 검사했는데,

parents를 이용하면 따로 visited를 만들 필요가 없다는 걸 깨닫고 코드를 수정하게 되었다.