(11725) 트리의 부모 찾기

문제

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

입력

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

출력

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

---

문제 풀이

해당 문제는 트리 자료구조를 활용하며 풀 수 있는 문제이다.

 

트리(Tree)는 그래프의 종류 중 하나로 root 노드와 부모노드 그리고 자식 노드가 존재한다. 즉, 계층 구조를 가지는 자료구조이다. 

 

해당 문제의 경우, 그래프를 먼저 만들어 주고 깊이 우선 탐색으로 1번 root 노드 부터 탐색을 한다. 다음 노드로 넘어 갈때 이전 노의 값을 기억하고 현재 노드의 기준 이전 노드를 배열에 입력 해주면 풀 수 있다.

 

아래는 예제 1번을 그래프로 구현 하게 되면 만들어지는 트리이다. 

이전 레벨에 노드와 간선으로 연결된 다음 노드간에 관계를 이해를 하여야 하는 문제이다.

---

나의 답안

import java.io.*;
import java.util.*;

public class Main {
    static List<Integer> graph[];
    static boolean[] visited;
    static int[] parents;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        parents = new int[n + 1];

        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1 ; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();

            graph[u].add(v);
            graph[v].add(u);
        }

        dfs(1, 0);

        for (int i = 2; i < n + 1; i++) {
            System.out.println(parents[i]);
        }

    }

    private static void dfs(int node, int parent) {
        parents[node] = parent;

        visited[node] = true;
        for (int next : graph[node]) {
            if (!visited[next]) dfs(next, node);
        }
    }

}