9938번

9938번 - 방 청소

이동할 수 있는 서랍을 parent 와 child 관계로 묶으면서 문제를 풀 수 있었다.

그리고 각 서랍이 술병이 들어있는지를 full 배열을 통해서 나타냈다.

규칙 3,4번을 어떻게 나타내야 할까 하다가, 끝까지 가보지 않더라도 find 함수를 통해, 제일 root값을 찾았을 때,

그 서랍이 비어있으면 규칙을 만족하므로, 다시 parent 를 재정의 하면서 문제를 풀 수 있었다.

처음에 술병을 이동시켜서 서랍을 바꿔주면, parent 와 child 관계를 일일이 거꾸로 표현을 어떻게 해야할지 고민했다.

그런데 조금 생각해보니까, root 만 바꿔주면, 모든 관계가 거꾸로 표현할 수 있다는 것을 깨달았다..

또 문제가 되었던 점은, 처음에 merge 함수를 쓰지 않고, 그냥 p[x]=a; 이런식으로 바꾸다 보니, 오류가 생겼다.

부모-자식 관계 정리가 제대로 되지 않고, 서로를 parent 로 가리켜서 무한히 재귀함수를 빠져나가지 못하는 case 가 발견되었다.

parent 를 재정의 할 때, 꼭 merge 함수를 사용해야 한다는 걸 깨달았다.

<정답 코드>

#include<iostream>
#include<vector>
using namespace std;
 
int p[300001];
//bool full[300001];
//bool drink[300001];
int find(int x)
{
    if (x == p[x])
    {
        return x;
    }
    else
    {
        return p[x] = find(p[x]);
    }
}
 
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
 
    if (x == y)
    {
        return;
    }
 
    p[x] = y;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, l;
    scanf("%d%d", &n, &l);
    vector<bool> full(l + 1);
    vector<bool> drink(n + 1);
    for (int i = 1; i <= l; i++)
    {
        p[i] = i;
    }
 
    for (int i = 1; i <= n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
 
        //규칙1
        if (!full[a])
        {
            full[a] = true;
            merge(a, b);
            continue;
        }
        //규칙2
        if (!full[b])
        {
            full[b] = true;
            merge(b, a);
            continue;
        }
        
        int x = find(a);
        //규칙3
        if (!full[x])
        {
            full[x] = true;
            merge(x, a);
            merge(a, b);
            continue;
        }
 
        x = find(b);
        //규칙4
        if (!full[x])
        {
            full[x] = true;
            merge(x, b);
            merge(b, a);
            continue;
        }
        //규칙5
        drink[i] = true;
    }
 
 
    for (int i = 1; i <= n; i++)
    {
        if (drink[i])
        {
            printf("SMECE\n");
        }
        else
        {
            printf("LADICA\n");
        }
    }
 
 
    return 0;
}