[백준] 9938: 방 청소

0. 문제 주소

 

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

9938번: 방 청소

 

 

1. 풀이

 

분리 집합 문제인 걸 몰랐으면 절대 못 풀었을 것 같다. 사실 알고도 엄청 오래 걸렸다.

 

1. 한 번 채워진 서랍은 절대로 비워지지 않고,

 

2. 여러 서랍이 연쇄적으로 이어지며 최종적으로 다음에 술을 넣을 서랍을 가리키는 것을 union find의 root로 구현할 수 있다.

 

 

2번이 진짜 어려웠는데... 구하고 나니까 코딩은 쉬웠다.

 

 

문제에 나온 예시로 간단히 설명을 해보자면,

 

 

(1, 2)가 주어졌을 때, 1번 서랍이 차있다고 bool 배열에 체크를 해주고, 1번 노드와 2번 노드를 merge해 준다.

 

이 때 2번 노드가 root가 되게 순서를 고려하여 merge 함수를 사용한다.

 

이는 만약 다음 순번에서 1번 서랍에 술을 넣고자 한다면, 1번 서랍에 있는 술이 2번 서랍의 술로 옮겨진다는 것이다.

 

그렇게 (3, 4), (5, 6), (7, 8), (9, 10) 술들을 차례로 적용시키고, 다음은 (2, 3)의 술이 들어왔다.

 

2번 서랍은 현재 비어있다. bool 배열에 2번 서랍이 찼다고 체크를 해주고 2번 노드와 3번 노드를 merge해 준다.

 

하지만 현재 3번 노드의 root는 4번 노드이므로, 결과적으로 2번 노드의 root는 4번 노드로 저장된다.

 

현재까지 1 ~ 4번 노드의 상황을 그림으로 정리하면 다음과 같다.

 

 

 

p[node] = -1이면 node는 root 노드라는 뜻으로 저장했다.

 

직관적으로 이해하기 위해 연결 관계와 표에서 1번의 root을 2번으로 표시했지만,

 

재귀적으로 "원래 저장되어있던 root의 root"로 root가 재설정되기 때문에

([PS/Union-Find] - [BOJ] 3830: 교수님은 기다리지 않는다 참고)

추후 p[1] = 4로 바뀐다.

 

어쨌든, 이후 1, 2, 3번 서랍에 술을 채우려 한다면 술을 옮기는 작업이 연쇄적으로 이루어져 4번 서랍까지 채워진다는 뜻으로 생각하면 된다.

 

merge(a, b)가 a의 root를 b로 설정하는 함수이고, (a, b) 의 술이 주어졌을 때, 문제에서 서술한 단계를 표현해보면

 

1. a번 서랍이 사용되지 않았으면 사용하고, a와 b (결과적으로는 a와 b의 root) 를 merge

2. b번 서랍이 사용되지 않았으면 사용하고, b와 a (b와 a의 root) 를 merge

3. a의 root가 사용되지 않았으면 사용하고, a의 root와 b (a의 root와 b의 root) 를 merge

4. b의 root가 사용되지 않았으면 사용하고, b의 root와 a (b의 root와 a의 root) 를 merge

5. 전부 안 되면 불가능

 

의 단계를 거치면 된다.

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <cstring>

#define MAX 300005

using namespace std;

int N, L;
int p[MAX];
bool has[MAX];

int find(int node){
    if (p[node] == -1) return node;
    return p[node] = find(p[node]);
}

void merge(int a, int b){
    int roota = find(a);
    int rootb = find(b);
    if (roota == rootb) return;
    p[roota] = rootb;
    return;
}

int main() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d %d", &N, &L);
    memset(p, -1, sizeof(p));
    int a, b;
    for (int i=0;i<N;i++){
        scanf("%d %d", &a, &b);
        if (!has[a]) {
            has[a] = true;
            merge(a, b);
            printf("LADICA\n");
        }
        else if (!has[b]){
            has[b] = true;
            merge(b, a);
            printf("LADICA\n");
        }
        else if (!has[find(a)]){
            has[find(a)] = true;
            merge(find(a), b);
            printf("LADICA\n");
        }
        else if (!has[find(b)]){
            has[find(b)] = true;
            merge(find(b), a);
            printf("LADICA\n");
        }
        else printf("SMECE\n");
    }
    

    return 0;
}