[백준/c++] 11725 트리의 부모 찾기

 

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

11725번: 트리의 부모 찾기

 

✨ 문제 풀이

BFS또는 DFS를 이용해서 해결할 수 있는 문제입니다.

 

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

연결된 노드의 정보가 위와 같다고 예시를 들어봅시다.

• 문제에 따르면 1은 무조건 루트 노드입니다. 따라서 1과 연결된 노드들은 모두 부모가 1인 노드입니다. 1과 연결된 노드는 4, 6입니다. 이 노드들에 대해서 차례대로 확인합니다.
• 4와 연결된 노드는 1, 2, 7 입니다. 1은 무조건 부모 노드이므로 2, 7이 자식 노드입니다. 즉 2, 7의 부모 노드는 4입니다.
  마찬가지로 6과 연결된 노드는 1, 3 입니다. 1은 무조건 부모 노드이므로 3이 자식 노드입니다. 즉 3의 부모 노드는 6입니다.
• 2와 연결된 노드는 4입니다. 4는 이미 방문한 노드이고 부모 노드입니다.
  7과 연결된 노드는 4입니다. 4는 이미 방문한 노드이고 부모 노드입니다.
  3과 연결된 노드는 5, 6입니다. 6은 이미 방문한 노드이고 부모 노드입니다. 자동으로 5는 자식노드입니다.
• 5와 연결된 노드는 3입니다. 3은 이미 방문한 노드이고 부모 노드입니다

이 연결 형태를 트리로 그려보면 아래와 같은 트리가 나옵니다.

 

위의 순서를 읽으면서 규칙을 발견할 수 있습니다. 루트 노드가 주어졌기 때문에, 연결된 노드 중에 방문한 적이 있는 노드는 무조건 부모노드이고, 방문한 적 없는 노드는 현재 노드의 자식 노드입니다. 다르게 말하면 자식 노드들의 부모 노드 번호는 현재 노드의 번호입니다!

방문한 적 있는 노드를 제외하고 탐색하는 방법인 BFS, DFS를 이용해서 차례대로 자식 노드들의 부모 노드를 현재 노드번호로 저장하고, 번호 순서대로 2번 노드부터 부모노드를 출력해주면 문제를 해결할 수 있습니다.

🗓 코드

1. DFS

#include <iostream>
#include <vector>

using namespace std;

#define MAXINT 100001

int n;
vector<int> node_v[MAXINT];

int result[MAXINT];
bool visited[MAXINT];

void getResult()
{
    for (int i = 2; i <= n; i++)
    {
        printf("%d\n", result[i]);
    }
}

void solve(int parent)
{
    for (int child : node_v[parent])
    {
        if (!visited[child])
        {
            visited[child] = true;
            result[child] = parent;
            solve(child);
        }
    }
}

int main(int argc, char const *argv[])
{

    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        node_v[u].push_back(v);
        node_v[v].push_back(u);
    }

    solve(1);
    getResult();
    return 0;
}

 

2. BFS

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define MAXINT 100001

int n;
vector<int> node_v[MAXINT];

int result[MAXINT];
bool visited[MAXINT];

void getResult()
{
    for (int i = 2; i <= n; i++)
    {
        printf("%d\n", result[i]);
    }
}

void solve(int start)
{
    queue<int> q;
    q.push(start);
    visited[start] = true;
    while (!q.empty())
    {
        int parent = q.front();
        q.pop();

        for (int child : node_v[parent])
        {
            if (!visited[child])
            {
                result[child] = parent;
                q.push(child);
                visited[child] = true;
            }
        }
    }
}

int main(int argc, char const *argv[])
{

    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        node_v[u].push_back(v);
        node_v[v].push_back(u);
    }

    solve(1);
    getResult();
    return 0;
}

 

 

위가 BFS로 해결했을 때, 아래가 DFS로 해결했을 때 결과입니다.

DFS가 시간은 더 빠르지만 메모리를 많이 사용하고, BFS는 시간은 상대적으로 오래 걸리지만 메모리를 절약합니다.