백준 2252 - 줄 세우기

문제

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

풀이

유니온파인드와 DFS를 이용해 풀이할 수 있는 문제였다.

• 키 순서는 방향 그래프로 해석할 수 있다. 키 큰 학생 -> 키 작은 학생 방향으로 간선을 설정해준다.
• 키 정렬 순서대로 그래프를 탐색하려면 가장 키 큰 학생(루트) 정보가 필요하다.
  • 키 순서를 입력받으며 유니온 파인드를 통해 키 큰 학생이 속한 분리집합의 자식으로 키 작은 학생을 추가한다. 결과적으로, 가장 키 큰 학생을 루트로 하는 분리집합이 형성된다.
  • 예제 1에서 1과 2가 3보다 키가 큰 건 알 수 있지만 1, 2의 순서는 알 수 없는데 입력 순서대로 유니온 해줄 경우 1 -> 3, 2 -> 1 -> 3 형태로 합쳐진다.(2, 1의 순서는 상관 x)
  • 유니온하며 부모 -> 자식 방향의 간선을 그래프에 추가해준다.
• 최적화된 parent 배열의 경우 parent[i]의 값이 음수일 때 i를 루트로 하는 분리 집합에 속한 노드 개수를, 양수일 경우 분리 집합내에서 i의 부모를 의미한다.
• parent 배열에서 부모 노드들을 추출해(parent[i] < 0) 해당 노드로부터 DFS 탐색을 진행하며 정답 출력값을 설정한다. 2개 이상의 분리 집합이 존재할 경우, 해당 분리 집합간 출력 순서는 상관 없으므로 탐색되는 대로 정답에 추가한다.

로직의 시간 복잡도는 최적화된 find 연산의 시간복잡도는 $O(\alpha(N))$이므로 입력 처리 과정에서 유니온 파인드를 수행하는 부분의 복잡도는 $O(m\alpha(N)))$이다. 한편, 각 루트에서 DFS를 수행하는 부분의 총 시간복잡도는 $O(N)$이다. 따라서, 전체 로직의 시간 복잡도는 $N=32,000$, $M=100,000$인 최악의 경우에도 무난히 제한 조건 2초를 통과한다.

참고 : $O(\alpha(N))$은 아커만 역함수 시간복잡도로 아커만 역함수는 입력이 10억이더라도 출력이 5 이하의 상수로 수렴하는 함수이다. 따라서 전체 복잡도에서 매우 적은 영향을 미친다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.IntStream;

import static java.lang.Integer.parseInt;

public class Main {
    static int[] parent;
    static List<List<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static StringBuilder answer = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());

        parent = new int[n + 1];
        Arrays.fill(parent, -1);

        graph.add(Collections.emptyList());
        IntStream.range(0, n).forEach(i -> graph.add(new ArrayList<>()));

        visited = new boolean[n + 1];

        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());

            int p1 = find(u);
            int p2 = find(v);

            if (p1 == p2) continue;

            parent[p1] += parent[p2];
            parent[p2] = p1;

            graph.get(p1).add(p2);
        }

        int[] parents = getParents();
        for (int parent : parents) {
            dfs(parent, 0);
        }

        System.out.println(answer.deleteCharAt(answer.length() - 1));
        br.close();
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

    static int[] getParents() {

        return IntStream.range(1, parent.length)
                .filter(i -> parent[i] < 0)
                .toArray();
    }

    static void dfs(int cur, int depth) {
        if (depth == graph.size() - 1) {
            return;
        }

        visited[cur] = true;
        answer.append(cur).append(" ");

        for (Integer next : graph.get(cur)) {
            if (visited[next]) continue;

            dfs(next, depth + 1);
        }
    }
}

결과