[백준 9938번] 방 청소

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

9938번: 방 청소

<문제 풀이> Union-Find(유니온-파인드), Disjoint-Set(서로소집합)

 

 

각 병에 대해서 A서랍, B서랍을 노드로 생각하고 그래프를 만듭니다. 여기서 부모 노드를 비어있는 서랍, 자식 노드를 병이 들어가 있는 서랍이라고 하면 그래프로 쉽게 문제를 해결할 수 있습니다.

 

서랍에 병을 넣을 때마다 넣었는지 여부를 체크해줍니다.

 

1. 서랍 A가 비어있다면 A를 자식 노드로 하고 B를 부모 노드로 한다. 

 

2. 서랍 B가 비어있다면 B를 자식 노드로 하고 A를 부모 노드로 한다.

 

3. 서랍 A에 부모 노드가 방문이 안됐으면(병을 옮길 수 있으면) 서랍 A에 부모 노드를 자식 노드로 하고 B를 부모 노드로 한다.

 

4. 서랍 B에 부모 노드가 방문이 안됐으면(병을 옮길 수 있으면) 서랍 B에 부모 노드를 자식 노드로 하고 A를 부모 노드로 한다.

 

서랍에 병이 들어있을 때 병을 다른 서랍으로 옮기는 과정들을 Union 연산으로 한 그래프를 만든다고 생각하고 빈 서랍을 찾는 데는 Find 연산으로 부모 노드를 찾는다고 생각하면 됩니다.

 

 

 

<C++ 소스 코드>

#include <iostream>
using namespace std;
 
int node[300001];
bool visited[300001];
 
int Find(int x) {
    if (x == node[x]) return x;
    return node[x] = Find(node[x]);
}
 
void Union(int x, int y) {
    int xParents = Find(x);
    int yParents = Find(y);
    node[xParents] = yParents;
}
 
int main(void) {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, L;
    
    cin >> N >> L;
    
    for (int i = 1; i <= L; i++) {
        node[i] = i;
    }
 
    while (N--) {
        int a, b;
        cin >> a >> b;
        if (!visited[a]) {
            visited[a] = true;
            Union(a, b); //a의 부모를 b로
            cout << "LADICA\n";
        }
        else if (!visited[b]) {
            visited[b] = true;
            Union(b, a); //b의 부모를 a로
            cout << "LADICA\n";
        }
        else if (!visited[Find(node[a])]) {
            visited[Find(node[a])] = true; 
            Union(a, b); //a의 부모를 b로
            cout << "LADICA\n";
        }
        else if (!visited[Find(node[b])]) {
            visited[Find(node[b])] = true;
            Union(b, a); //b의 부모를 a로
            cout << "LADICA\n";
        }
        else {
            cout << "SMECE\n";
        }
    }
 
    return 0;
}