[백준] 11725 - 트리의 부모 찾기 (JAVA)

SILVER II

문제

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

입력

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

출력

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

풀이

난이도 보고 쉽게 풀 수 있겠거니 했다가, 통수에 통수를 맞은 문제였다.

일단 문제의 풀이 방향은 이렇다.

1. 주어지는 입력값을 그래프로 만든다.
2. 1번 노드부터(1번은 무조건 root이므로) 차례대로 그래프를 탐색한다. BFS든 DFS든 상관없으나 나는 BFS를 사용하였다.
3. 1번 노드와 연결된 노드는 무조건 1번 노드를 부모로 갖는다.
4. 이미 부모를 찾은 노드와 연결된 노드들은 그 노드를 부모로 갖는다. (트리이므로.)

이렇게 모든 노드를 순회하여 탐색하면 모든 노드들의 부모 노드를 찾을 수 있다.

나는 이 과정에서 두 가지 문제에 직면했다.

인접 행렬 그래프

보통 문제 풀이를 할 때, 나는 인접 행렬 방식을 이용해 그래프를 표현한다. 이 방법이 익숙해졌기 때문이고 쉽기 때문이다. (정확히는 쉽다고 생각하고 있었다.)

하지만 이 방식은 무조건 주어지는 노드의 수(n)만큼의 크기를 갖는 배열을 할당해주어야 한다는 문제가 있다. 즉, 시작하자마자 무조건 n*n 크기의 메모리를 소모하게 된다.

그래서 인접 리스트 방식을 이용해 그래프를 표현해주었다.

인접 리스트 방식이 왜 더 메모리를 적게 소모하는가?

만약 1000개의 노드가 주어졌다고 가정했을 때, 인접 행렬이라면 무조건 1000*1000을 할당해주어야 한다. 하지만 인접 리스트라고 한다면, 1000*(각 노드와 연결된 edge 수)만큼의 크기만 잡아먹게 된다.

그러므로 생으로 Array를 쓰는 것이 아니라 List를 이용하면 쉽게 구현할 수 있다.

이렇게 일단 메모리 초과는 해결했다.

LinkedList vs ArrayList

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

그래프를 할당할 List를 선언하는 부분이다. 여기서 무엇이 문제일까?

LinkedList와 ArrayList에서 특정한 원소를 찾아가는 방식을 생각해보면 쉽게 답을 알 수 있다.

LinkedList는 특정한 원소를 찾아가려면, 무조건 이전 index를 거쳐야만 한다. 그렇기에 BFS 등을 하는 과정에 있어서 시간을 엄청나게 잡아먹을 수밖에 없는 것이다.

만약, graph.get(10000)을 하려고 한다면, 0번 원소부터 10000번까지 차례대로 거쳐가야 한다. 하지만 ArrayList는 한 번에 그 값으로 찾아간다. 이 부분에서 시간이 차이가 나게되는 것이었다.

따라서 위의 LinkedList를,

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

이렇게 바꾸면 된다.

(그냥 맨 처음부터 ArrayList로 사용했으면 이런 문제도 없었을 텐데. 뭐, 그래도 삽질 해보면서 크게 배웠으니 좋다고 생각해야지 뭐.)

전체 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;

        int n = Integer.parseInt(br.readLine());

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

        int[] parent = new int[n+1];
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < n-1; i++) {
            stk = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(stk.nextToken());
            int node2 = Integer.parseInt(stk.nextToken());

            graph.get(node1).add(node2);
            graph.get(node2).add(node1);
        }

        queue.add(1);
        parent[1] = 1;

        while(!queue.isEmpty()) {
            int node = queue.remove();
            for (int value : graph.get(node)) {
                if (parent[value] == 0) {
                    parent[value] = node;
                    queue.add(value);
                }
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 2; i <= n; i++)
            bw.write(parent[i] + "\n");

        bw.flush();
        bw.close();
    }
}