(매일 BOJ) C++ 11725번 트리의 부모 찾기

이번 문제는 트리의 부모 찾기이다

문제 요약

정점 1을 루트(root) 로 하는 트리가 주어진다. 각 간선은 무방향이며, 정점 수는 N, 간선 수는 N-1
목표는 정점 2부터 N까지 각각의 부모 정점을 출력하는 것이다

 

접근법

트리는 연결되어 있고 사이클이 없다

 루트(1)에서 한 번 BFS(또는 DFS) 를 돌면서 “처음 방문”한 정점의 부모를 누가 찍었는지 기록하면 끝

• 시작: 1을 큐에 넣고 시작
• 인접 정점 v를 처음 만났다면 parent[v] = u
• 큐가 빌 때까지 반복 → parent[2..N] 출력

시간 복잡도는 인접 리스트 기준으로 O(N)이다

 

작성코드

아래 코드는 BFS로 부모를 구한다. 입력 이후 인접 리스트를 정렬해(선택 사항) 작은 번호부터 탐색하도록 했다

#include <bits/stdc++.h>
using namespace std;

void BFS (vector<int> & perent, vector<vector<int>> & vertex);
int N;

int main (void){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> N;
    
    vector<vector<int>> vertex(N+1);
    for(int i = 1; i < N; i++){
        int a,b;
        cin >> a >> b;
        vertex[a].push_back(b);
        vertex[b].push_back(a);
    }

    for(int i = 1; i <= N; i++){
        sort(vertex[i].begin(),vertex[i].end());
    }

    vector<int> perent(N+1,-1);
    BFS(perent,vertex);

    for(int i = 2; i <= N; i++){
        cout << perent[i] << '\n';
    }

    return 0;

}

void BFS (vector<int> & perent, vector<vector<int>> & vertex){
    queue<int> q;
    q.push(1);
    vector<bool> visited(N+1,false);
    visited[1] = true;

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

        for(int next : vertex[current]){
            if(!visited[next] && perent[next] == -1){
                perent[next] = current;
                q.push(next);
            }
        }

    }

}