방 청소( BOJ 9938 )

문제 : https://www.acmicpc.net/problem/9938

9938번: 방 청소

 

문제 파악하기

N개의 술병을 서랍에 넣을 수 있는지 확인하는 문제입니다. 술병은 각각 정해진 2개의 서랍(A, B) 중 비어있는 위치에 넣을 수 있으며, 이미 서랍에 들어있는 술병을 연쇄로 이동하여 빈 자리가 생기게 만들 수도 있습니다. 다만 술병을 넣는 서랍은 우선순위가 있는데 A와 B 중 비어있는 서랍에 우선적으로 넣어야 하며, 두 서랍에 모두 넣을 수 있다면 A에 먼저 넣어야 합니다. 서랍이 비어있는 경우에는 간단하게 찾을 수 있지만, 서랍에 이미 술병이 들어있는 경우에는 연쇄로 이동시킬 수 있는지 여부를 직접 확인하기에는 서랍과 술병의 개수가 많기에 시간 내에 확인하기는 불가능합니다. 따라서, 문제를 좀 더 간단하게 변화시킬 필요가 있습니다.

그럼 어떻게 문제를 간단하게 바꿀 수 있을까요? 만약 A, B 서랍 중 한 곳이 비어있는 경우에는 간단하게 바로 서랍에 넣으면 됩니다. 문제는 두 개의 서랍이 모두 채워있는 경우입니다. 이 경우에는 서랍에 들어있는 술병을 연쇄로 이동해야 하는데, 생각해보면 모든 술병을 이동시키면서 확인할 필요가 없습니다. 연쇄 이동의 가장 끝에 위치한 술병만 이동할 수 있으면 나머지 술병은 자연스럽게 이동할 수 있기 때문입니다. 따라서, 우리는 가장 끝에 위치한 술병을 확인해서 이동시킬 수 있는지 여부를 확인하여 문제를 해결할 수 있습니다.

 

문제 해결하기

그럼 가장 끝에 위치한 술병을 어떻게 찾을 수 있을까요? 다행히 이런 작업에 특화된 자료구조가 있습니다. 바로 분리집합(union-find)을 사용하면 간단하게 구현할 수 있습니다. 분리 집합을 사용하여 현재 술병이 들어갈 수 있는 서랍과 이동할 수 있는 서랍을 연결하면 연쇄 이동을 표현할 수 있습니다. 예를 들어 A와 B 서랍 중 A 서랍에 술병을 넣을 수 있다면, num[A] = B 와 같이 표현하여 현재 A 서랍에 들어있는 술병은 B로 옮길 수 있다고 표시할 수 있습니다. 이처럼 모든 num[ ] 배열을 초기화한 다음, 들어간 술병을 모두 분리 집합을 통해 연결하면서 발생할 수 있는 모든 경우를 처리한다면 우리는 마지막에 위치한 술병의 이동 여부를 빠르게 파악할 수 있습니다.

 

술병을 서랍에 넣으면서 나올 수 있는 경우의 수는 총 2가지입니다.

첫 번째, 서랍에 아무 술병도 안 들어있는 경우입니다. 이 경우에는 num[ ] 배열의 값이 초깃값이기 때문에 서랍에 넣고 연결해주면 됩니다. 단, A와 B 서랍 모두 넣을 수 있다면 A 서랍부터 먼저 넣어야 하기에 조건문의 순서를 제대로 정해야 합니다.

두 번째, 서랍에 술병이 들어있는 경우입니다. 이 경우에는 연결된 술병 증 가장 끝에 위치한 술병을 확인해야 하며, 이 때 find( ) 연산을 통해 찾을 수 있습니다. 그리고 만약 가장 끝에 위치한 술병이 초깃값이라면 술병을 넣고, 새롭게 연결해주면 됩니다. 다만, 연결할 때에는 다음 연결된 서랍이 싸이클을 형성하는지 확인해야 합니다. 싸이클을 형성하게 되면 find( ) 연산 시, 무한루프를 발생시키기 때문에 적절한 처리가 필요합니다.

 

이렇게 경우의 수에 따라 서랍에 연결을 적절하게 하면 직접 술병을 옮기는 시뮬레이션을 거치지 않아도 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#define NMAX 300010
using namespace std;
 
int N, L, a, b;
int f, pa, pb;
int num[NMAX];
 
int find(int p) {
    if(p == num[p] or num[p] == -1) return p;
    else return num[p] = find(num[p]);
}
 
int main() {
    scanf("%d %d", &N, &L);
    memset(num, -1, sizeof(num));
 
    for(int i=0;i<N;i++) {
        scanf("%d %d", &a, &b);
 
        f = 1;
 
        pa = find(a);
        pb = find(b);
 
        if(num[a] == -1) {
            if(pa != pb) num[a] = b;
            else num[a] = a;
        }
        else if(num[b] == -1) {
            if(pa != pb) num[b] = a;
            else num[b] = b;
        }
        else {
            if(num[pa] == -1) {
                num[pa] = a;
                num[a] = -1;
 
                pa = find(a);
                pb = find(b);
 
                if(pa != pb) num[a] = b;
                else num[a] = a;
            }
            else if(num[pb] == -1) {
                num[pb] = b;
                num[b] = -1;
 
                pa = find(a);
                pb = find(b);
 
                if(pa != pb) num[b] = a;
                else num[b] = b;
            }
            else f = 0;
        }
 
        if(f == 1) printf("LADICA\n");
        else printf("SMECE\n");
    }
}

후기

흥미로운 분리 집합 문제였습니다. 감으로는 분리 집합을 활용해야 할거 같은데 어떻게 해야 모든 경우를 처리하는지 떠올리는데 시간이 걸렸던 문제입니다. 구현이 크게 어렵지 않았던 문제라 더더욱 좋았던 문제라고 생각합니다. 알고리즘 대회를 준비하는 사람에게 추천하고 싶은 문제입니다.