[백준] 11725번 : 트리의 부모 찾기

#문제

11725번: 트리의 부모 찾기

https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

---

#접근방법

루트가 1인 트리에서 n-1개의 엣지가 주어질 때, 2 ~ n번 노드의 부모를 찾는 문제이다.

 

두 노드를 입력 받을 때, 두 노드가 서로 연결되어 있다는 표시를 하고 dfs(깊이 우선 탐색)으로 각 노드의 부모를 구해주면 된다.

반응형

---

#풀이

#include <stdio.h>
#include <vector>
using namespace std;

vector<int> v[100005];
int ans[100005]={1};

void dfs(int x){

    for(int i=0;i<v[x].size();i++){
        int k = v[x][i];

        if(ans[k]==0){
            ans[k] = x;
            dfs(k);
        }
    }

    return;
}

int main(){
    int n;
    int x,y;

    scanf("%d",&n);

    for(int i=0;i<n-1;i++){
        scanf("%d %d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }

    dfs(1);

    for(int i=2;i<=n;i++)
        printf("%d\n",ans[i]);

    return 0;
}

 

 

 

반복문으로 두 노드를 입력 받을 때, 서로 연결이 되어있다는 표시를 해줘야 한다.

 

2차원 배열로 v[x][y] = 1, v[y][x] = 1로 연결 시켜주는 방법이 있고,

 

vector 자료구조를 사용하여 v[x].push_back(y), v[y].push_back(x)로 연결 시켜주는 방법이 있다.

 

이 문제에서는 노드의 개수가 100,000개까지 주어질 수 있으므로 2차원 배열로 하면 100000 * 100000 / 2^20 = 약 9536MB 이므로 메모리 초과가 걸린다.

 

따라서 vector 자료구조를 사용하여 인접배열로 연결시켜줘야 한다.

 

연결을 시켜주었으면 dfs(깊이 우선 탐색)으로 노드 1부터 인접 노드로 탐색을 하면서 ans 배열에 부모노드를 넣어 주면 된다.

 

단, 이미 탐색한 노드가 있을 수 있으므로 조건문으로 이미 탐색한 노드, 즉 ans[x]에 값이 들어 있는 경우에는 탐색을 하지 않으므로써 무한 탐색을 막아줘야 한다.

 

ans배열을 2부터 n까지 출력하면 정답이다.

---

#성능

---

#정리

문제 조건에 따라서 두 노드를 연결하는 방법을 정할 수 있고 dfs, 또는 bfs를 알면 풀 수 있는 문제였다.