[백준 BOJ 11725번] 트리의 부모 찾기 (C++ ) [트리/DFS/BFS]

11725번: 트리의 부모 찾기 (acmicpc.net)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	256MB	19371	8219	6123	43.364%

문제

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

입력

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

출력

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

예제 입력 1

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1

4
6
1
3
1
4

예제 입력 2

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

예제 출력 2

1
1
2
3
3
4
4
5
5
6
6

실수

 인접리스트 방식으로 풀려고 손으로 필기를 하는 도중에 해당 노드들의 바로 다음 노드 값이 예제 출력과 동일하다는 것을 발견했다.

 예제1번을 예로들면,

1번 노드를 제외하는 것을 깜빡했는데 2번 노드 부터 보면 예제 출력 1과 동일한 것을 알 수 있다. 게다가 예제 2도 동일했다. 솔직히 정석적으로 풀어보려고 했지만 50%에 육박하는 정답률을 보고, 눈에 선히 보이는 함정에 또 제 발을 넣어버렸다. 당연히 오답 처리가 되었다.

코드

// 트리의 부모 찾기
// 그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N;
queue<int>q;
vector<int>v[100001];
int parent[100001];
void bfs(){
    while(!q.empty()){
        int curr=q.front();
        q.pop();
        for(int i=0;i<v[curr].size();i++){
            int next=v[curr][i];
            if(parent[curr]==next)continue;
            q.push(next);
            parent[next]=curr;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    cin>>N;
    for(int i=1;i<N;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    q.push(1);
    bfs();
    for(int i=2;i<=N;i++)cout<<parent[i]<<"\n";
}

11725번: 트리의 부모 찾기 (acmicpc.net)

11725번: 트리의 부모 찾기