백준) 9938 방 청소

9938. 방 청소

문제

은기는 술병 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번 술을 그 자리에서 마셔버린다. (은기는 전혀 취하지 않는다)

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

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ N, L ≤ 300,000)

다음 N개 줄에는 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ L, Ai ≠ Bi)

출력

1번 술부터 N번 술까지 순서대로 보관할 수 있는지, 그 자리에서 먹어야 하는지를 출력한다.

보관할 수 있는 경우에는 "LADICA"를, 먹어버려야 하는 경우에는 "SMECE"를 출력한다.

예제 입력 

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

예제 출력 

LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA

1. 접근

L개의 빈 서랍이 있다. 서랍은 술병을 단 하나만 보관할 수 있으며, 1~N번이 적힌 술병은 보관될 수 있는 서랍이 A/B로 지정되어 있다.

술병들의 보관장소가 1번 술병부터 주어지고 규칙에 따라 바로 보관시킬 때, 보관할 수 있는지 없는지 확인해야 한다.

규칙은 다음과 같다.

1) A 서랍이 비었으면 바로 A에 보관

2) B 서랍이 비었으면 바로 B에 보관

3) A 서랍이 비지 않았으면 A서랍이 보관 중인 술병이 보관될 수 있는 다른 서랍으로 연쇄적으로 옮긴다.

즉, 최종적으로 빈 서랍을 찾을 때 까지 계속 술병을 규칙에 따라 옮겨야 한다.

4) B 서랍이 비지 않았다면 3)과 동일 하게 옮긴다.

5) 옮길 수 없다.

서랍을 노드로 생각하고, A/B를 간선이라 생각해보면

예제의 첫째 줄 " 1 2 " 는 1번 노드와 2번 노드를 잇는 간선으로 이해할 수 있다.

1번 노드가 불가능하면(이미 보관 중인 서랍이면) 1)규칙이 불가능하므로 2)규칙을 시도한다. (유향 간선을 타고 다음 노드로 간다)

2번 노드도 불가능하면 2번 노드에서 출발하는 다음 간선으로 가는 과정으로 이해할 수 있다.

2. 풀이

그래프적 분석을 완료했으니 실제로 그래프를 구현하고 매번 탐색을 시도하는 방법을 생각해 볼 수도 있다.

다음 예시 입력을 통해 어떤 변화가 생기는지 알아보자.

4 3

1 2

1 3

1 2

1 3

1번 술병은 곧바로 1번 서랍에 보관되고(주황색으로 표시), 다음 차선책으로 2번 서랍을 가리키고 있다.

1번 노드의 루트노드가 2다.

이제 2번 술병의 보관 장소가 주어지는데, 하필 1번 술병이 보관되고 있는 1번 서랍을 1순위로 두고 있다.

따라서 1번 술병을 차선책인(간선을 타고 이동해서) 2번 서랍에 보관하고, 2번 술병은 1번 서랍에 보관하자.

또한 2번 술병의 차선책인 3번 서랍을 간선으로 이어준다.

1번 노드의 루트 노드가 3으로 변경되었다.

3번 술병도 1순위로 1번 서랍을 원한다. 다행히 현재 1번 서랍이 보관하는 2번 술병은 3번 서랍에 보관될 수 있으므로 옮겨준다.

이제 1번 서랍은 3번 술병을 보관할 수 있다. 차선책인 2번 서랍을 간선으로 이어준다. 1번 노드의 루트 노드가 변경되었다.

당연히 이제 1번 서랍을 1순위로 원하는 술병이 주어지면 어디에도 보관될 수가 없다.("SMECE")

착안점은 한 노드에서 나가는 간선은 최대 1개라는 점이다. 이 점에서 우리는 디스조인트 셋을 쓸 수 있고, 속도의 이점을 얻는다.

대신 간선들의 모양은 위의 그림들과는 다르게 적용될 것이다.

( (1/2) 이후 (1/3)을 입력받으면 2에서 3으로 간선이 생긴다 )

루트노드가 중요한 역할을 한다. 연쇄적으로 수행되는 3), 4) 규칙의 최종적인 빈서랍 역할을 하는 것이다.

노드가 보관 중인지 아닌지는 간단히 배열로 나타낸다.

3. 코드

#include <stdio.h>
using namespace std;
 
int n, l, a, b, i;
bool taken[300001];
int parent[300001];
 
int find(int x) {
    if (x == parent[x])
        return x;
    else
        return parent[x] = find(parent[x]);
}
 
void unite(int x, int y) {
    x = find(x);
    y = find(y);
    parent[x] = y;
    puts("LADICA");
}
 
int main() {
    scanf("%d %d", &n, &l);
    for (i = 1; i <= l; ++i) {
        parent[i] = i;
    }
    for (i = 0; i < n; ++i) {
        scanf("%d %d", &a, &b);
        if (!taken[a]) {
            taken[a] = true;
            unite(a, b);
        }
        else if (!taken[b]) {
            taken[b] = true;
            unite(b, a);
        }
        else if (!taken[find(a)]) {
            taken[find(a)] = true;
            unite(a, b);
        }
        else if (!taken[find(b)]) {
            taken[find(b)] = true;
            unite(b, a);
        }
        else
            puts("SMECE");
    }
    return 0;
}