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

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 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

풀이

DFS를 이용해서 문제를 풀었고, 인접행렬을 이용했다.

 

예제1을 예시로 들면,

 

[1] 6 4

[2] 4

[3] 6 5

[4] 1 2 7

[5] 3

[6] 1 3

[7] 4

 

로 입력받은 배열을 넣어주고, DFS를 이용하여 부모노드를 탐색한다. 

 

 

//11725. 트리의 부모 찾기
#include <iostream>
#include <vector>
 
using namespace std;
 
bool visited[100001];
int parent[100001];
vector<int> v[100001];
 
void dfs(int currentNode){
    visited[currentNode] = true;
 
    for(int i=0; i<v[currentNode].size(); i++){
        int nextNode = v[currentNode][i];
        
        if(!visited[nextNode]){
            parent[nextNode] = currentNode;
            dfs(nextNode);
        }
    }
}
 
int main(){
    int N;
    cin >> N;
    for(int i=0; i<N-1; i++){
        int firstNode, secondNode;
        cin >> firstNode >>  secondNode;
 
        v[firstNode].push_back(secondNode);
        v[secondNode].push_back(firstNode);
    }
 
    dfs(1);
 
    for(int i=2; i<=N; i++){
        cout << parent[i] << "\n";
    }
 
    return 0;
}