BOJ11725 트리의 부모 찾기

https://www.acmicpc.net/problem/11725 (opens new window)

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구한다.

깊이 우선 탐색

DFS를 활용하여 풀이 하였다. 트리의 루트는 1로 정해져 있기 때문에 1부터 DFS를 진행하며 parent 배열에 부모 노드를 저장한다.

private static void dfs(int x) {
    for (int i = 0; i < graph.get(x).size(); i++) {
        int y = graph.get(x).get(i);
        if (parent[y] == 0) {
            parent[y] = x;
            dfs(y);
        }
    }
}

제출 코드

아래는 최종 제출 코드이다.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BOJ11725 {

    private static List<List<Integer>> graph = new ArrayList<>();
    private static int[] parent;

    private static void dfs(int x) {
        for (int i = 0; i < graph.get(x).size(); i++) {
            int y = graph.get(x).get(i);
            if (parent[y] == 0) {
                parent[y] = x;
                dfs(y);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 노드의 개수

        parent = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            // 양방향 그래프
            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        parent[1] = 1;
        dfs(1);

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 2; i <= n; i++) {
            stringBuilder.append(parent[i]).append("\n");
        }

        System.out.println(stringBuilder);
    }
}

주의할 점!

TIP

여기서 List는 주로 탐색을 위주로 사용된다. 그렇기 때문에 ArrayList를 사용하여 구현해야 한다.

#BOJ #그래프 이론 #그래프 탐색 #트리 #너비 우선 탐색 #깊이 우선 탐색