[Baekjoon] 백준 9938번: 방 청소 (c++)

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

9938번: 방 청소

문제가 이해가 안가서 구글 검색으로 Union Find문제라는 걸 알아냈다... ㅠㅠ 검색 없이 솔루션 찾는걸 연습해야하는데... 예제를 봐도 이해가 잘 안갔다. 코드는 맨 아래!

 

 

아래 설명을 꼭 이해해야 문제를 풀 수 있다. 규칙 1 2 3 4 5 순서대로 실행해야 한다

1. 서랍 Ai가 비어있다면, i번 술을 그 서랍에 보관한다.
2. 서랍 Bi가 비어있다면, i번 술을 그 서랍에 보관한다.
3. Ai에 들어있는 술을 다른 서랍으로 이동시킨다.(다른 서랍은 Ai에 들어있는 술이 들어갈 수 있는 서랍 중 하나이다) 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Ai에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
4. Bi에 들어있는 술을 다른 서랍으로 이동시킨다. 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Bi에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
5. 위의 과정이 모두 불가능한 경우에는 i번 술을 그 자리에서 마셔버린다. (은기는 전혀 취하지 않는다)

 

예제 Input에 대해 내가 푼 방법을 설명하자면

9 10
1 2
3 4
5 6
7 8
9 10
2 3
1 5
8 2
7 9

맨 첫줄 9 10 은 각각 술병 개수(입력 수), 노드 수

둘째줄 부터는 Aᵢ , Bᵢ 의 입력이 주어진다.

1 2

3 4
5 6
7 8
9 10

입력까지는

1번 서랍에 술1 할당, 1번 서랍이 꽉찼을 경우 2번 서랍에 할당 parent[1] = 2      drawer[1] = 1

3번 서랍에 술3 할당, 3번 서랍이 꽉찼을 경우 4번 서랍에 할당 parent[3] = 4    drawer[3] = 1

5번 서랍에 술5 할당, 5번 서랍이 꽉찼을 경우 6번 서랍에 할당 parent[5] = 6     drawer[5] = 1

... parent[7] = 8       drawer[7] = 1 

... parent[9] = 10        drawer[9] = 1

 

 

2 3 입력이 들어오면 

2번 서랍은 아직 비었으므로 2번 서랍에 술2 할당. 2번 서랍이 꽉 찼을 경우 3번에 할당. 그런데 3번 서랍은 꽉찼을경우 4번에 할당하므로 4번을 루트노드로 표시 parent[2] = 4    drawer[2] = 1

 

1 5 입력이 들어오면

1번 서랍은 꽉찼고, 2번 서랍도 꽉찼으므로 규칙3에 따라

3. Ai에 들어있는 술을 다른 서랍으로 이동시킨다.(다른 서랍은 Ai에 들어있는 술이 들어갈 수 있는 서랍 중 하나이다) 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Ai에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.

 1번 서랍에 들어있는 술을 2로, 2번 서랍에 들어있는 술을 3으로, 3번 서랍에 들어있는 술을 4번으로 옮김

그리고 1번의 루트를 5로 할당해야 하지만, 5번 서랍이 찼을 때 6번에 할당하므로 1번의 루트는 6으로 지정

parent[1] = 6    drawer[4] = 1

 

8 2 입력이 들어오면

8번 서랍은 비었으므로 8번 서랍에 술8 할당, 8번 서랍이 꽉찼을 때는 8번서랍을 2번 서랍의 루트 6로 지정.

parent[8] = 8     drawer[8] = 1

 

7 9 입력이 들어오면

7번 서랍은 꽉찼으므로 차선책 8번을 확인, 8번의 루트는 6번이므로  루트로 가는 과정 중 빈 서랍은 6번이니 6번노드에 할당

7번 서랍이 꽉 찼을경우, 9번노드의 루트인 10을 7의 루트로 지정.

parent[7] = 10      drawer[6] = 1

 

**술은 루트 노드에 바로 할당하는 것이 아니라, 루트로 가는 과정 중 빈 서랍이 있다면 거기에 할당해야 함

아래 그림을 보면 이해가 잘된다. 

병이 든 서랍에는 형광색으로 표시해두었다

parent는 빈 서랍, drawer는 빈 서랍인지 확인하는 배열으로 두었다.

1. drawer[0]은 사용하지 않으므로 1로 초기화, parent는 전부 자기자신으로 초기화

2. 입력받은 a, b로 Union함수 실행

    - a의 부모, b의 부모를 각각 찾아 parent[a] = b 로 할당

 

3. a에 대하여 Find함수 실행

    3.1 a의 부모가 자기 자신이라면, 비어있는 노드이므로 drawer[x] = 1; flag = true;  실행 후 return x

    3.2 a의 부모가 자신이 아니라면 자신의 부모 parent[x]에 대하여 Find함수 호출. parent[x]가 비어있다면 drawer[parent[x]] = 1; flag = true; 비어있지 않다면 다시 parent[x]의 부모에 대하여 Find함수 호출을 반복.

 

4. 3.1과 3.2를 모두 끝냈음에도 flag == false라면, SMECE 출력.   flag == true면 빈 서랍에 할당 될 수 있으므로 LADICA 출력.

 

 

 

 핵심 코드는 Find함수의 첫번째 줄이다

    if(!flag && drawer[x] == 0) { drawer[x] = 1; flag = true; }

Union전에 flag = false를 해 두고,

a와 b의 부모를 찾을 때 만약 해당 서랍이 비었고( drawer[x] == 0 ), 한 번도 술병을 넣은 적이 없다면 ( flag == false ) 

drawer[x] = 1, flag = true를 할당해준다. 반복문이 한 번 돌 때, 술병은 입력받은 a 에 대하여 한번만 할당할 수 있으므로 flag처리를 해준 것!

 

처음에 간과했던 것은, drawer 배열에 0이 하나라도 있으면 비어있는 거니까 LADICA를 출력하면 되겠다고 생각했는데, 

a의 루트를 따라 이동해도 술병을 할당 할 수 없는 경우가 생긴다. 예시는 아래 접은글에..

5 5 // N L
1 2
1 3
1 2
4 5
1 3

위와 같은 예시의 경우, 
1 2
1 3
1 2
4 5 까지는 LADICA를 출력하지만,

1 3 입력이 들어온 경우, 노드5는 비어있지만, 1 - 2 - 3       4 - 5    이렇게 연결되어있기 때문에 술병1을 어디에도 할당 할 수 없다.

 

---

코드(c++)

#include <string>
#include <vector>
#include <iostream>
using namespace std;
#define MAX 300000

int drawer[MAX] = {0,};
int parent[MAX] = {0,};
bool flag = false;

int Find(int x){
    
    if(!flag && drawer[x] == 0) { drawer[x] = 1; flag = true; }
    
    if(x == parent[x]) return x;
    return parent[x] = Find(parent[x]);
}
void Union(int a,int b){
    a = Find(a);
    b = Find(b);
    if(a!=b) parent[a] = b;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   
    int N, L, a, b;
    
    cin >> N >> L;
    drawer[0] = 1;
    for(int i=1;i<=L;i++)parent[i] = i;
    for(int i=0;i<N;i++){
        cin >> a >> b;
        flag = false;
        Union(a, b);
        
        if(flag == false) cout << "SMECE\n";
        else cout << "LADICA\n";
    }
  
    return 0;
}

 

코드로 짜는건 어렵지 않은데 솔루션 찾는게 어려워서 등급이 높은가보다. 그래두 해결하고 나니 플래티넘3이라 뭔가 기분좋았던..✨