[11725] 트리의 부모 찾기(C++)

 

문제 

[11725] 트리의 부모 찾기

 

 

해결 방법

이 문제도 전형적인 dfs, bfs 문제이다.

한 가지, 현재 노드의 부모 노드가 몇번인지 저장할 배열만 추가하면 된다.

나는 인접리스를 활용한 dfs로 구현하였는데,

인접한 노드를 모두 입력받은 후 리스트의 형태는 아래와 같다.

노드
1	6	4
2	4
3	6	5
4	1	2	7
5	3
6	1	3
7	4

1번 노드부터 탐색을 시작하는데, 1번 노드와 연결된 노드는 무조건 1번 노드의 자식임을 알아두자.

또한, 나와 연결된 노드는 나의 부모이거나 자식이거나 둘중 하나임을 기억하자.

탐색을 하면서 나와 연결되어있지만 이미 방문한 노드는 부모노드이고, 그렇지 않은 노드는 부모 노드가 아니기에 자식노드로 판단하고 부모로 저장해주면 된다!

 

 

내 코드(C++)

// [11725] 트리의 부모 찾기
// https://www.acmicpc.net/problem/11725

#include <iostream>
#include <vector>
using namespace std;

int n; // 노드의 개수
bool visited[100001] = {false};
int parent[100001];
vector <int> tree[100001];

void dfs(int start)
{
    visited[start] = true;
    for(int i = 0 ; i < tree[start].size() ; i++) {
        int next = tree[start][i];
        if(visited[next] == false) {
            parent[next] = start; // 부모 노드부터 탐색하기 때문에 연결되어있고 방문하지 않은 다음 노드는 무조건 자식 노드
            dfs(next);
        }
    }
}

int main(void)
{
    int n1, n2; // 두 정점
    cin >> n;
    for(int i = 0 ; i < n-1 ; i++) {
        cin >> n1 >> n2;
        tree[n1].push_back(n2); tree[n2].push_back(n1);
    }

    parent[tree[1][0]] = 1; parent[tree[1][1]] = 1; // 1번 노드와 연결되어있는 노드들의 부모는 1
    dfs(1);

    for(int i = 2 ; i <= n ; i++) {
        cout << parent[i] << '\n';
    }

    return 0;
}