[백준 117253 - C++] 트리의 부모 찾기 : DFS

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

 

풀이

이 문제는 루트가 1이라고 할때, 각각의 노드의 부모가 누구인지 찾는 문제이다. 따라서 1부터 dfs탐색을 시작하여 재귀로 dfs함수를 다시 호출하게 될 때 마다 그 함수를 호출하는 함수의 노드를 부모로 저장하면 된다.

이 문제에서 노드의 개수는 최대 10만개로 매우 크기 때문에 연결된 map을 저장하는 데에는 2차원 배열을 사용하지 않고 벡터를 사용하였다. 메모리 누수를 줄이기 위해서!!

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int visited[100001];
int t_parent[100001];
vector<vector<int>> map;

void dfs(int n, int now);

int main(void){
    int n;
    int a, b;
    
    scanf("%d", &n);
    map.resize(n+1);
    
    for(int i=0; i<n-1; i++){
        scanf("%d %d", &a, &b);
        map[b].push_back(a);
        map[a].push_back(b);
    }
    
    dfs(n, 1);
    
    for(int i=2; i<=n; i++){
        printf("%d\n", t_parent[i]);
    }
}

void dfs(int n, int now){
    int next;
    
    visited[now] = 1;
    
    for(int i=0; i<map[now].size(); i++){
        next = map[now][i];
        if(visited[next] == 1)
            continue;
        
        t_parent[next] = now;
        dfs(n, next);
    }
}