[백준] 방청소(9938)

문제 링크 : [백준] 방청소(9938)

문제 설명

술병이 N개, 서랍이 L개가 있고, 술병_i를 각각 두 후보의 서랍 A_i, B_i에 넣을 수 있는데,

1. A_i 서랍이 비어있다면 A_i 서랍에 술병을 넣습니다.
2. A_i 서랍이 비어있지 않고, B_i 서랍이 비어있다면, B_i 서랍에 술병을 넣습니다.
3. A_i, B_i 서랍 둘다 비어있지 않으면, A_i에 있는 병을 다른 서랍에 옮기고, 빈 자리에 병을 넣는다. 옮기는 방법은 해당 병이 갈 수 있는 다른 서랍입니다.
4. 3이 불가능한 경우, B_i 서랍에 있는 병을 3과 같은 방법으로 옮깁니다.
5. 어떤 방법으로도 옮길 수 없다면 먹습니다.

입력

N(병의 갯수, 1<=N<=300,000)
L(서랍의 갯수, 1<=L<=300,000)
A_i B_i(병을 놓을 서랍 번호, N줄이 반복되어 나옴, 1<=A_i,B_j<=L, A_i!=B_i)

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

출력

보관 할 수 있으면 LADICA
보관 할 수 없으면 SMECE

LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA
LADICA

카테고리

#DisjointSet

시간 복잡도 상한

N,L 모두 30만이므로, 각각의 제곱이나, N*L의 풀이 방법은 되지 않습니다.
O(NlogL)이나 O(LlogN)이나 O(N), O(L) 등의 방법으로 풀어야 합니다.

해결 방법

1. A_i, B_i가 비어 있는 경우, 그냥 넣으면 됩니다.
2. 두 곳 모두 비어있지 않다면 빈 곳에 대한 탐색을 시작합니다.
3. DFS 등으로 탐색하면 O(N*L)의 시간복잡도가 되어 타임아웃이 발생합니다.
4. 문제 설명 중, 두 군데가 모두 비어있지 않는 경우에 대해 잘 파악해보면,
   빈병_i는 A_i와 연결 된 그룹 G_A와 B_i와 연결 된 그룹 G_B 중 빈 곳을 찾아 병을 넣게 되고, G_A와 G_B는 빈병_i에 의하여 하나의 그룹으로 연결됩니다.
5. 따라서 A_i의 그룹과, B_i의 그룹 중에 빈 곳이 없다면 SMECE를 출력하고, 빈 곳이 있다면, LADICA를 출력하고, 두 그룹을 하나로 합칩니다.
   5-1. 그룹을 합칠 때는, 각 그룹의 빈병의 합도 같이 관리합니다.
6. 그룹을 관리하는 것은 DisjointSet을 이용하여 시간복잡도를 줄일 수 있습니다.

코드

#include<cstdio>
int n,m,d[300001],i,a,b,v[300001];
int f(int a){
    if(a==d[a])return a;
    return d[a]=f(d[a]);
}
void u(int a,int b){
    d[f(a)]=f(b);
}
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)d[i]=i,v[i]=1;
    while(n--){
        scanf("%d%d",&a,&b);
        int fa=f(a);
        int fb=f(b);
        if(v[fa]>0||v[fb]>0)printf("LADICA\n");
        else printf("SMECE\n");

        if(fa==fb){
            if(v[fa])v[fa]--;
        }else{
            u(a,b);
            v[fb]=v[fa]+v[fb]-1;
        }
    }
}