백준 - 11725번(트리의 부모 찾기)

문제 출처: https://www.acmicpc.net/problem/11725

문제

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

• 시간 초과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine()); // 노드의 개수

        int[] parents = new int[N + 1]; // 1-base index
        parents[1] = 1;

        Queue<int[]> queue = new ArrayDeque<>();

        // 입력 받기
        for (int i = 0; i < N - 1; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int x = Integer.parseInt(tokenizer.nextToken()); // 첫 번째 수
            int y = Integer.parseInt(tokenizer.nextToken()); // 두 번째 수

            queue.offer(new int[] { x, y });
        }

        while (!queue.isEmpty()) {
            int[] temp = queue.poll();

            if (parents[temp[0]] != 0) { // x가 부모가 되는 경우
                parents[temp[1]] = temp[0];
            } else if (parents[temp[1]] != 0) { // y가 부모가 되는 경우
                parents[temp[0]] = temp[1];
            } else queue.offer(temp);
        }

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

        System.out.println(sb);
    }

}

• 정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    private static List<Integer>[] nodeList;
    private static int[] parents;
    private static boolean[] decision;

    public static void main(String[] args) throws IOException {
        StringBuilder sb = new StringBuilder();
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine()); // 노드의 개수

        parents = new int[N + 1]; // 1-base index
        parents[1] = 1;

        decision = new boolean[N + 1]; // 부모가 확정됐는지 여부
        decision[1] = true; // 1번은 루트 노드이므로 부모가 확정됨

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

        for (int i = 0; i < N - 1; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int x = Integer.parseInt(tokenizer.nextToken());
            int y = Integer.parseInt(tokenizer.nextToken());

            if (decision[x]) { // x의 부모가 확정된 경우
                decision[y] = true;
                parents[y] = x;
                dfs(y);
            } else if (decision[y]) { // y의 부모가 확정된 경우
                decision[x] = true;
                parents[x] = y;
                dfs(x);
            } else {
                nodeList[x].add(y);
                nodeList[y].add(x);
            }
        }

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

        System.out.println(sb);
    }

    private static void dfs(int num) {
        for (int i = 0, size = nodeList[num].size(); i < size; i++) {
            if (!decision[nodeList[num].get(i)]) {
                decision[nodeList[num].get(i)] = true;
                parents[nodeList[num].get(i)] = num;
                dfs(nodeList[num].get(i));
            }
        }
    }

}

• 처음에 Queue를 이용한 방식을 생각해내어 풀었으나 시간초과가 나왔다. 꽤 잘 정리된 로직이라 생각했는데 우울했다...
• 처음 생각한 로직은, 입력으로 들어오는 두 수 중 어느 한쪽이 부모가 확정된 수이면 다른 한쪽은 자식이 되는 성질을 이용하여 어느 한쪽이 확정된 경우에는 처리하고 둘 다 확정되지 않으면 Queue의 끝에 넣어 원형 큐로 풀었다.
• 그러나 54%에서 시간초과가 나왔다.
• 문제 질문에 있는 글을 조금 참고하여 새로운 로직을 구상했다.
• 먼저, 기존처럼 어느 한쪽이 부모가 정해진 경우는 똑같이 다른 한쪽을 자식으로 처리한다.
• 그런데 만약 둘 다 부모가 정해지지 않은 수가 들어올 경우, 두 수 각각 자신의 리스트에 추가한다(nodeList). 이 리스트는 인덱스에 해당하는 노드와 연결된 노드를 나타내는 리스트다.
• 사실 어느 한쪽의 부모가 정해진 연산을 수행할 때 뒤에 하나의 연산이 더 수행된다.
• DFS를 통해 자식으로 정해진 수에 연결된 다른 수가 있는지 확인한다. 만약 수가 존재할 경우, 그 수들은 모두 자식이 되므로 부모를 정하는 연산을 수행하고, 이를 더 이상 연결된 수가 없을 때까지 반복한다.