[BOJ/tree] 11725 트리의 부모 찾기

강신현·2021년 10월 30일
0
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/*
트리의 루트 : 1

각 노드의 부모 노드를 구함 -> 모든 노드 탐색 -> dfs(재귀 or 스택), bfs(큐)

문제유형
1) 그래프의 모든 정점을 방문하는 것이 주요한 문제 (dfs && bfs)

단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
둘 중 편한 것을 사용하시면 됩니다.

2) 경로의 특징을 저장해둬야 하는 문제 (dfs)

예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

3) 최단거리 구해야 하는 문제 (bfs)

미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

이밖에도 
- 검색 대상 그래프가 정말 크다면 DFS를 고려
- 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

출처: https://devuna.tistory.com/32 [튜나 개발일기]
*/

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

void dfs(int node)
{
    visited[node] = true; // 방문 표시

    for (int i = 0; i < tree[node].size(); i++)
    {
        int target = tree[node][i];

        if (!visited[target])
        {
            // 입력할때 부모 -> 자식 순으로 입력하므로, 인자(node -> tree[node][i])가 부모노드이다.
            parent[target] = node;

            // 재귀를 통한 dfs 탐색
            dfs(target);
        }
    }
}

queue<int> que;
void bfs(int node)
{
    que.push(node);
    visited[node] = true;

    while (!que.empty())
    {
        int cur = que.front();
        que.pop();

        for (int i = 0; i < tree[cur].size(); i++)
        {
            int target = tree[cur][i];

            if (!visited[target])
            {
                parent[target] = cur;

                que.push(target);
                visited[target] = true;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N - 1; i++)
    {
        int node1, node2;
        cin >> node1 >> node2;

        tree[node1].push_back(node2);
        tree[node2].push_back(node1);
    }

    // dfs(1);

    bfs(1);

    // 부모 노드 번호를 2번 노드부터 순서대로 출력
    for (int i = 2; i <= N; i++)
    {
        cout << parent[i] << '\n';
    }

    return 0;
}
profile
땅콩의 모험 (server)

0개의 댓글