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

문제

백준 11725 문제 보기

접근 방법

bfs를 통해 부모를 찾아 저장하면 정답을 출력할 수 있다. 입력시 양방향을 다 고려해야 하는 것에 주의.

코드

#include <iostream>
#include <queue>

using namespace std;

int N;
int parents[100001];
int visited[100001];

vector<vector<int>> tree(100001);
queue<int> q;

int main() {

    cin >> N;

    int i, j;

    // 양방향을 고려해 입력
    for(int x = 0; x < N-1; x ++) {
        cin >> i >> j;
        tree[i].push_back(j);
        tree[j].push_back(i);
    }

    // 루트 노드는 부모가 없으므로 처리하고 큐에 저장
    parents[1] = 0;
    q.push(1);
    visited[1] = 1;

    while(!q.empty()) {
        int a = q.front();
        q.pop();
        // 연결된 노드에 접근한 적이 없다면 접근하고 방문처리 및 부모 설정
        for(int b : tree[a]){
            if(!visited[b]) {
                visited[b] = 1;
                parents[b] = a;
                q.push(b);
            }
        }
    }

    // 출력
    for(int i = 2; i <= N; i++) {
        cout<< parents[i] << '\n';
    }

    return 0;
}