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

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

11725번: 트리의 부모 찾기

 

문제

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

입력

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

출력

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

 

풀이

간선 정보를 입력받아 인접 그래프로 저장한다

루트 (1) 부터 bfs로 탐색한다

-> 현재 a를 탐색하고있고 자식 b를 발견

-> b를 큐에 집어넣기 전 b의 부모노드가 a라는 사실을 입력 (parent[b] = a)

-> 출력

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    // 입력
    int n, a,b;
    cin >> n;
    vector<vector<int>> graph(n+1);
    for(int i=0; i<n-1; i++) {
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    // parent[i] = i의 부모
    vector<int> parent(n+1);
    
    // bfs
    vector<bool> visit(n+1, false);
    visit[1] = true;
    queue<int> q;
    q.push(1);
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        for(int i : graph[cur]) {
            if(visit[i])
                continue;
            parent[i] = cur;
            visit[i] = true;
            q.push(i);
        }
    }
    
    // 출력
    for(int i=2; i<=n; i++)
        cout << parent[i] << "\n";
    
    return 0;
}