[자바] 백준 2843 - 마블 (java)

 문제 : boj2843

---

 

필요 알고리즘 개념

• 오프라인 쿼리 (offline query)
  
  • 쿼리(질의)의 순서를 변경해서 푸는 아이디어를 생각해낼 수 있어야 한다.
• 분리 집합 (disjoint set)
  
  • 분리 집합 개념과, 분리집합에서 집합이 합쳐지는 방향을 강제할 수 있어야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  이 문제에서는 조약돌이 멈추는 정점을 묻는 쿼리와 간선을 지우는 쿼리가 존재한다. 일반적으로 간선을 지우는건 어려운 일이다. 따라서 보통 간선을 지워야 하는 경우라면, 역으로 간선을 생성해서 풀 수 없는지 살펴봐야 한다.

 

  이 문제에선 가능한데, 실시간으로 처리하는 시스템이 아니라 이미 입력이 모두 들어온걸 보고 처리하면 되는 알고리즘 문제라 그렇다. 모든 쿼리를 알고 있으므로, 역순으로 순서를 바꾸게 되면 이 문제에서 간선을 지우는 쿼리는 다음과 같이 변경된다.

- 2 X : 정점 X에서 나가는 간선을 추가한다.

- 1 X : 이건 동일하다.

 

  그럼 조약돌이 멈추는 위치는 어떻게 알 수 있을까? 이 문제는 방향 그래프이고, 조약돌은 방향을 가지고 움직인다. 따라서 매번 DFS를 해주면 알 수 있다. 근데 N이 30만이나 되므로 O(QN)이 필요해서 이 경우 시간초과가 날 것이다. 간선을 지우는 경우에는 분리 집합을 쓸 수 없지만, 간선을 연결하면서는 분리 집합을 당연히 사용할 수 있다. 그리고 분리 집합에서 부모 노드를 항상 방향 조약돌이 이동하는 방향이 부모가 된다고 해보자. 즉, A정점과 B정점에 대해 A->B 인 상태였다면 A와 B를 union할 시 B가 부모가 되도록 강제하는것이다. 그럼 단순히 해당 그룹의 부모 정점 번호만 알면 그곳이 조약돌이 멈추는 곳이다.

 

  멈추지 않고 무한히 이동하는 조약돌은 어떻게 알 수 있을까? MST(Minimum Spanning Tree)를 알고있다면 얘기가 빠른데, Kruskal 알고리즘으로 MST 구현 시 일반적으로 분리 집합 알고리즘을 사용해 사이클이 생기는지 확인한다. 사이클 얘기가 왜나왔냐면 사이클이 생길 경우 조약돌이 무한으로 이동하기 때문이다. 로직은 간단한데, 분리 집합에서 union 시에 두 정점의 그룹 부모가 동일한 번호라면 사이클이 발생한거다. 합치는 곳이 동일한 곳이니깐! 

 

  그럼 문제를 풀기위해 필요한 아이디어 및 알고리즘은 다 나온 것 같으니 로직을 정리하면 아래와 같다.

1. N개의 간선 정보를 기록만 해둔다.

2. Q개의 쿼리를 입력받으면서 미리 '2 X' 쿼리에 나왔던 X들을 기록해둔다.

3. 이제 '1'의 간선 정보를 가지고 간선을 연결해주는데, '2'에서 나왔던 끊겼던 간선들은 제외하고 연결한다.

4. 이제 쿼리를 역순으로 보면서 '2 X' 쿼리라면 집합을 union 해준다. 이 때, union할 두 정점이 이미 동일한 그룹이었다면 사이클이 발생한 경우이므로 별도로 기록해둔다.

5. '1 X' 쿼리라면 X 정점의 그룹 부모 정점 번호를 출력해준다. 다만 '4'에서 사이클이 발생한 지점이라면 CIKLUS를 출력해준다.

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

class Query {
    int op, x;
    public Query(int op, int x) {
        this.op = op;
        this.x = x;
    }
}

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final int OP_ERASE = 2;
    private static final int OP_QUERY = 1;
    private static final int UF_ROOT = -1;
    private static final int UF_CYCLE = -2;

    int[] parents;
    boolean[] cycle;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private boolean isCycle(int a) {
        return parents[find(a)] == UF_CYCLE;
    }

    private int find(int a) {
        if (parents[a] < 0)
            return a;
        return parents[a] = find(parents[a]);
    }

    private void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a==b) {
            parents[b] = UF_CYCLE;
            return;
        }
        parents[a] = b;
    }

    public void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        parents = new int[n+1];
        cycle = new boolean[n+1];
        Arrays.fill(parents, UF_ROOT);
        int[] edge = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            edge[i] = Integer.parseInt(st.nextToken());
        }

        int q = Integer.parseInt(br.readLine());
        Query[] queries = new Query[q];
        HashSet<Integer> except = new HashSet<>();
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int op = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            queries[i] = new Query(op, x);
            if (op == OP_ERASE)
                except.add(x);
        }

        for (int i = 1; i <= n; i++) {
            if (except.contains(i) || edge[i] == 0) continue;
            union(i, edge[i]);
        }

        ArrayList<Integer> answer = new ArrayList<>();
        for (int i = q-1; i >= 0; i--) {
            if (queries[i].op == OP_QUERY) {
                answer.add(isCycle(queries[i].x) ? UF_CYCLE : find(queries[i].x));
            } else {
                int a = queries[i].x;
                int b = edge[a];
                if (b!=0)
                    union(a, b);
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = answer.size()-1; i >= 0; i--) {
            sb.append(answer.get(i) == UF_CYCLE ? "CIKLUS" : answer.get(i)).append('\n');
        }
        System.out.print(sb);
    }
}