11725 트리의 부모 찾기

11725 트리의 부모 찾기 (c++)

문제

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

접근 방식

BFS
트리가 있을 때 두 노드 중 어느 노드가 부모일 지 모른다.

1. 부모 노드가 있는 노드가 있다면 아닌 노드가 자식으로 들어간다.
2. 부모 노드가 없다면 둘다 인접 노드에 추가해 놓고
   1. 나중에 부모가 정해지면 인접 노드 중 부모가 없는 노드들을 자식 노드로 추가

문제 풀이

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

int N;
int p[100'001] = {};
vector<int> adj[100'001] = {};

void SetParent(int now)
{
    for (int i = 0; i < adj[now].size(); ++i)
    {
        if (p[adj[now][i]]) continue;
        p[adj[now][i]] = now;
        SetParent(adj[now][i]);
    }
}

int main()
{
    scanf("%d", &N);

    p[1] = 1;

    int A, B;
    for (int i = 1; i < N; ++i)
    {
        scanf("%d %d", &A, &B);
        if (!p[A] && !p[B])
        {
            adj[A].push_back(B);
            adj[B].push_back(A);
        }
        else
        {
            if (p[A])
            {
                p[B] = A;
                SetParent(B);
            }
            else
            {
                p[A] = B;
                SetParent(A);
            }
        }
    }

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

    return 0;
}

다시 생각해 볼 점

1. 다시 생각하는 거지만, BFS는 단순 그래프가 알고리즘이 아니다. (물론 여긴 노드와 간선이 있는 트리였지만)
2. 이 경우는 인접노드를 탐색하는 순서가 BFS로 실행된 것이다. (둘다 부모가 없을 때 인접노드에 서로를 저장하고, 이 후 부모가 결정되면 인접노드를 BFS로 탐색하며 자식노드로 저장)