[9938번] 방 청소

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Union Find :: http://www.crocus.co.kr/683

[4195번] 친구 네트워크 :: http://www.crocus.co.kr/686 이 문제를 푼 사람이라면 방 청소 문제는 쉽게 접근 할 수 있을 것이고,

친구 네트워크 문제를 풀어보지 않았다면 방 청소 문제 다음 저 문제를 풀어보는 것을 추천한다.

이 문제는 각 서랍에 술병이 1개만 있어야하고, 그 술병을 어떻게 옮겨가며 최종적으로 마실지 혹은 안마시고 보관할지 결정해야 한다.

이 문제를 접근하기 위한 몇가지 생각이 든다.

유니온 파인드로 인해 일단 노드들이 뭉쳐지는 생각은 해 볼 수 있다.

하지만 이걸 노드간에 이동하면서 술을 옮긴다.. 이건 매우 시간 복잡도면에서도 무너질 가능성이 높고 구현 자체도 까다로워 보인다.

따라서 이 문제를 그냥 단순하게 생각해보자.

유니온 파인드로 뭉쳐진 트리는 k개의 노드를 가지고 있을 것이다. 이때 k개의 노드수 자체가 보관 할 수 있는 개수를 의미한다.

따라서 술병이 매번 들어올 때 마다 그 해당하는 트리의 루트 노드가 보관 가능 개수를 컨트롤 해주면 된다.

하나 들어오면 -1, 만약 트리가 합쳐지는 과정이면 a트리의 노드 개수 + b트리의 노드 개수 -1 

이런식으로 방에 공간이 남았는지를 판단하여  마신다, 안마시고 보관한다를 결정한다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <string>
 
#define swap(a,b){int t = a; a = b; b = t;}
 
using namespace std;
 
typedef pair<int, int> pii;
 
int node;
 
// first :: 부모 표현 second :: 자신을 포함한 자식 노드 개수 표현
pii parent[300001];
int level[300001];
 
int find(int u)
{
    // 루트 노드이면 return u
    if (u == parent[u].first)
        return u;
    
    // 그 외에는 자신의 루트를 찾으러 간다.
    return parent[u].first = find(parent[u].first);
}
 
void merge(int u, int v)
{
    u = find(u);
    v = find(v);
 
    // 루트가 같다면 이미 같은 트리
    if (u == v)
    {
        if (parent[v].second - 1 < 0)
            printf("SMECE\n");
        else
        {
            parent[v].second--;
            printf("LADICA\n");
        }
        return;
    }
 
    // u가 v보다 더 깊은 트리라면 swap
    if (level[u] > level[v])
        swap(u, v); // 항상 u가 더 작은 트리가 되도록 한다. 
 
    // u의 루트가 v가 되도록
    parent[u].first = v;
 
    // u와 v의 깊이가 같을 때 v의 깊이를 늘려준다.
    if (level[u] == level[v])
        ++level[v];
 
    // 루트 노드에는 항상 아래 노드의 총 합 개수를 저장해준다고 생각하면
    if (parent[v].second + parent[u].second - 1 < 0)
        printf("SMECE\n");
    else
    {
        parent[v].second += parent[u].second - 1;
        printf("LADICA\n");
    }
 
}
 
int main()
{
    int n, m;
 
    scanf("%d %d", &n, &m);
 
    // 초기화
    for (int i = 1; i <= m; i++)
    {
        parent[i].first = i;
        parent[i].second = 1;
        level[i] = 1;
    }
 
    while (n--)
    {
        int s1, s2;
        scanf("%d %d", &s1, &s2);
 
        merge(s1, s2);
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>