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

입/출력

• 입력: 노드의 개수 N (2 ≤ N ≤ 100,000), 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점
• 출력: N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력

 

제출 코드

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

using namespace std;

void search(int n,vector< vector<int> > &tree, vector<int> &visit, vector<int> &answer){
    queue<int> q;

    q.push(n);
    visit[n] = 1;

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

        for(int num : tree[current]){
            if(!visit[num]){
                visit[num] = 1;
                answer[num]=current;
                q.push(num);
            }
        }
    }
}

int main(){
    int N;

    // 노드 수 입력
    scanf("%d", &N);

    vector< vector<int> > tree(N+1);
    vector<int> visit(N+1);
    vector<int> answer(N+1);

    fill(visit.begin(), visit.end(),0);
    fill(answer.begin(), answer.end(),0);

    // 노드 별 연결된 두 정점 입력
    for(int i=0; i<N-1; i++){
        int x,y;

        scanf("%d %d", &x, &y);
        tree[x].push_back(y);
        tree[y].push_back(x);
    }

    search(1,tree,visit,answer);
    
    for(int i=2; i<=N; i++){
        printf("%d\n",answer[i]);
    }

    return 0;
}

• 단방향인데 상위노드 식별 위해 연결된 정점은 모두 해당 노드에 대한 벡터에 넣기
• 이미 방문한 노드면 연결된 정점보다 상위 노드로 연결된 노드의 루트로 표시
• 시간초과 문제 - BFS인데 DFS처럼 계속 재귀호출해서 시간초과 발생했었음. 재귀호출 대신 queue에 push하는 식으로 진행함.

 

제출 결과