[Baekjoon] 11725번: 트리의 부모 찾기 - Java

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

11725번: 트리의 부모 찾기

문제 설명

제목이 트리의 부모 찾기라서 트리를 구현해야 하나 싶지만 인접 리스트 그래프로 복잡하지 않게 해결할 수 있다. 트리도 그래프의 부분집합이다. 사이트 예제 1을 활용하여 그려보면 다음과 같다. 각 노드의 부모를 구하는 게 문제이기 때문에 DFS나 BFS로 루트(1)부터 연결된 노드들을 탐색해 나가면 된다.

위 그림을 토대로 코드의 흐름을 그려보면 다음과 같다.

DFS(1)
  DFS(6)
    DFS(3)
      DFS(5)
  DFS(4)
    DFS(2)
    DFS(7)

풀이 방법 1. DFS

private static void dfs(int index) {
    isVisited[index] = true;
    for (Integer i : tree[index]) {
        if (!isVisited[i]) {
            answer[i] = index;
            dfs(i);
        }
    }
}

풀이 방법 2. BFS

private static void bfs() {
    Queue<Integer> queue = new LinkedList<Integer>();
    queue.add(1);
    isVisited[1] = true;
    while (!queue.isEmpty()) {
        Integer vertex = queue.remove();
        for (Integer node : tree[vertex]) {
            if (!isVisited[node]) {
                isVisited[node] = true;
                queue.add(node);
                answer[node] = vertex;
            }
        }
    }
}

전체 코드는 다음과 같다.

package baekjoon.dfs_bfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ11725 {

    static int N;
    static ArrayList<Integer>[] tree;
    static boolean[] isVisited;
    static Integer[] answer;

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            N = Integer.parseInt(br.readLine());

            tree = new ArrayList[N + 1];
            isVisited = new boolean[N + 1];
            answer = new Integer[N + 1];

            for (int i = 1; i <= N; i++) {
                tree[i] = new ArrayList<>();
            }

            for (int i = 0; i < N - 1; i++) {
                int[] edgeInfos = Arrays.stream(br.readLine().split(" "))
                        .mapToInt(Integer::parseInt).toArray();

                tree[edgeInfos[0]].add(edgeInfos[1]);
                tree[edgeInfos[1]].add(edgeInfos[0]);
            }

            // dfs(1);
            bfs();

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

            System.out.print(sb);
        }
    }

    private static void dfs(int index) {
        isVisited[index] = true;
        for (Integer i : tree[index]) {
            if (!isVisited[i]) {
                answer[i] = index;
                dfs(i);
            }
        }
    }

    private static void bfs() {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.add(1);
        isVisited[1] = true;
        while (!queue.isEmpty()) {
            Integer vertex = queue.remove();
            for (Integer node : tree[vertex]) {
                if (!isVisited[node]) {
                    isVisited[node] = true;
                    queue.add(node);
                    answer[node] = vertex;
                }
            }
        }
    }
}