백준 9938번 방 청소 :: 마이구미

이 글은 백준 알고리즘 문제 9938번 "방 청소" 를 풀이한다.

풀이 방법으로는 디스조인트-셋 자료구조를 이용한다.

개인적으로 보면, 굉장히 어려운 문제가 된다.

문제 링크 - https://www.acmicpc.net/problem/9938

디스조인트 셋 이해 - http://mygumi.tistory.com/246

은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다.  서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다.

은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대해서 다음과 같은 과정을 거친다.

1. 서랍 Ai가 비어있다면, i번 술을 그 서랍에 보관한다.
2. 서랍 Bi가 비어있다면, i번 술을 그 서랍에 보관한다.
3. Ai에 들어있는 술을 다른 서랍으로 이동시킨다.(다른 서랍은 Ai에 들어있는 술이 들어갈 수 있는 서랍 중 하나이다) 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Ai에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
4. Bi에 들어있는 술을 다른 서랍으로 이동시킨다. 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Bi에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
5. 위의 과정이 모두 불가능한 경우에는 i번 술을 그 자리에서 마셔버린다. (은기는 전혀 취하지 않는다)

각각의 술에 대해서, 서랍에 보관할 수 있는지, 그 자리에서 마셔버리는지를 구하는 프로그램을 작성하시오.

문제에서 명시한 과정의 순서를 정확하게 이해해야한다.

오해할 수 있는 것은 서랍의 형태이다.

서랍은 A, B 두 개로 나누어져 있지 않고, 한 서랍에서 Ai, Bi 를 따로 입력으로 주어지는 것이다.

이것이 의미하는 바는 우선순위라고 생각하면 된다.

1 3 이 주어진다면, 먼저 서랍 1에 넣을 수 있다면, 1에 넣고 그럴 수 없다면 2에 넣는 것이다.

즉, 노드는 서랍, 간선은 서랍이 이동할 수 있는 Ai의 차선책 Bi과 같은 관계라고 볼 수 있다.

과정을 이해하고 조금 더 생각한다면, 이동에 있어서 깊게 생각하지 않아도 된다.

3, 4번의 과정으로 술을 이동시키더라도, 술을 보관했던 이전 서랍에는 항상 술이 존재한다.

술이 이동하면서 서랍에 대한 술의 여부는 변할 수 있지만, 이동시키기 전의 서랍은 술이 바뀔 뿐, 술의 여부는 변하지 않는다. (빈 서랍이 아니라는 말)

결과적으로 말하고자하는 것은 한번 채워진 서랍은 절대 비워지지 않는다는 것이다.

그렇기에 단순 방문 여부 배열이 이용될 수 있다는 것을 알 수 있다.

단순히 서랍을 채울 수 있으면 채우고, 그렇지 못하면, 연결된 차선책을 확인하면 된다.

다음 예제를 풀이 코드에 대해 그림으로 표현하면 다음과 같다,

9 10
1 2
3 4
5 6
7 8
9 10
2 3
1 5
8 2
7 9

6번째까지는 과정 1을 통해 순조롭게 보관할 수 있다.

각 노드는 서랍을 나타내고, 간선은 서랍 Ai, Bi 관계를 나타낸다.

현재 2, 4, 6, 8, 10, 3 이 루트 노드가 된다.

루트 노드는 빈 서랍을 위한 용도로 사용된다.

1 5가 주어졌을 때는 서랍 1이 채워져있기 때문에, 과정 2를 간다.

하지만 서랍 5도 채워져있기 때문에, 과정 3으로 간다.

그 결과는 다음과 같다.

8 2이 주어졌을 때, 서랍은 8은 비워있기 때문에, 술을 넣는다.

과정 1를 처리하지만, 다음 차선책인 서랍 2는 이미 술이 있기 때문에, 2의 루트인 6를 바라보게 된다.

다음과 같다.

7, 9이 주어졌을 때, 7의 차선책인 8이 비어있기 때문에 과정 3을 처리한다.

최종 결과는 다음과 같다.

find 처리에서 압축을 하고 있기 때문에 다소, 복잡하게 보일 수 있다.

단순히 서랍을 채울 수 있다면 채우고, 채울 수 없다면, 한단계 위에서 채워줄 수 있는 지 확인하면 되는 문제이다.

중요한 건, 루트 노드의 역할과 변화를 이해하면 된다.

링크 - 디스조인트-셋 문제 카테고리 

Github - https://github.com/hotehrud/acmicpc/tree/master/algorithm/disjoint-set

static int[] parent = new int[300001];
static boolean[] visited = new boolean[300001];
static StringBuilder sb = new StringBuilder();
 
private void solve() {
    int n = sc.nextInt();
    int l = sc.nextInt();
 
    for (int i = 1; i <= l; i++) {
        parent[i] = i;
    }
 
    for (int i = 1; i <= n; i++) {
        int a = sc.nextInt();
        int b = sc.nextInt();
 
        if (!visited[a]) {
            visited[a] = true;
            merge(a, b);
        } else if (!visited[b]) {
            visited[b] = true;
            merge(b, a);
        } else if (!visited[find(parent[a])]) {
            visited[find(parent[a])] = true;
            merge(a, b);
        } else if (!visited[find(parent[b])]) {
            visited[find(parent[b])] = true;
            merge(b, a);
        } else {
            sb.append("SMECE\n");
        }
    }
    System.out.println(sb.toString());
}
 
public static void merge(int u, int v) {
    u = find(u);
    v = find(v);
    parent[u] = v;
    sb.append("LADICA\n");
}
 
public static int find(int u) {
    if (u == parent[u]) {
        return u;
    }
    return parent[u] = find(parent[u]);
}
 
public static void main(String[] args) {
    sc.init();
 
    new Main().solve();
}