[알고리즘 풀이 분석] BOJ 11725 트리의 부모 찾기

실버 2 단계의 그래프 탐색 문제 BOJ 11725 트리의 부모 찾기 풀어보았다.

BOJ 11725 트리의 부모 찾기

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입출력

[입력]
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

[출력]
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

나의 풀이

풀이 방법은 깊이 우선 탐색을 이용하는 것이다.

우선 주어지는 노드 갯수가 최대 100000 개 이기 때문에 인접 행렬을 사용하는 것은 메모리 초과가 날 것이라 생각했다. 최대 100000 개의 노드별로 인접한 노드만 저장해 두고 사용했다.

트리의 루트가 1이기 때문에 1부터 깊이 우선 탐색을 시작한다. 현재 노드를 기준으로 인접한 노드 중 방문하지 않은 노드가 있다면 방문하고 해당 과정을 재귀적으로 반복한다. 방문을 진행하면서 부모 노드를 일차원 배열에 입력 해 두도록 한다.

탐색이 끝나면 완성된 부모 노드 배열을 2부터 N 까지 출력한다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> adjacent[100001];
bool visited[100001];
int parent[100001];

void dfs(int cur) {
    visited[cur] = true;

    for (int i = 0; i < adjacent[cur].size(); ++i) {
        int adj = adjacent[cur][i];
        if (visited[adj]) continue;
        parent[adj] = cur;
        dfs(adj);
    }
}

int main() {
    int N;
    cin>>N;

    for (int i = 0; i <N-1; ++i) {
        int a, b;
        cin>>a>>b;
        adjacent[a].push_back(b);
        adjacent[b].push_back(a);
    }

    dfs(1);

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

    return 0;
}