[BOJ 9938] 방 청소(Java, Union-Find, 문제 이해하기)

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

9938번: 방 청소

 

 

 

 

## 접근

---

• 서랍에 대한 boolean 배열을 통해서, 서랍의 비어있는 유무를 파악하도록 한다.
  
  
• 서랍이 가득찼을 때, 규칙3과 규칙4에 말하는 다른 서랍의 의미를 파악하는 것이 중요하다. 다른 서랍의 핵심은 기존의 들어있는 술을 옮길 수 있는 서랍이여야 한다. 다른 서랍들에 대한 저장할 수 있는 자료구조가 필요하다.
  
  
• 서랍에 기존의 술이 있을 때, 기존의 술을 옮기기 위해서는 모든 서랍의 다른 서랍을 저장해두어야 한다. 빈 서랍을 찾기 위해서, 서랍들은 재귀적으로 호출될 것이다. 하지만, 매번 서랍들이 재귀적으로 호출된다면 시간 복잡도가 증가한다. 따라서, 특정한 서랍이 가득찼을 때, 최종적으로 확인해야 하는 서랍만 저장해야 한다
  
  
• 서랍의 다른 서랍을 저장하는 것을 Union으로, 최종적으로 확인해야 하는 서랍만 저장하도록 하는 것은 Find으로 해결할 수 있다.

 

 

 

 

## 해설코드

---

import java.lang.*;
import java.io.*;
import java.util.*;
 
public class Main{
    static int[] root;
    static boolean[] chk;
    
    static int find(int x){
        if(x == root[x])
            return x;
        else
            return root[x] = find(root[x]);    
    }
    
    static void union(int x, int y){
        root[find(x)] = find(y);
    }
    
     public static void main(String []args) throws java.lang.Exception{
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
         
         int N, L, A, B;
         String answer;
        
         String[] sArr = br.readLine().split(" ");
         N = Integer.valueOf(sArr[0]);
         L = Integer.valueOf(sArr[1]);
         
         root = new int[L + 1];
         chk = new boolean[L + 1];
          
         for(int i = 0; i < root.length; i++) root[i] = i;
         
         for(int i = 1; i <= N; i++){
            sArr = br.readLine().split(" ");
            A = Integer.valueOf(sArr[0]);
            B = Integer.valueOf(sArr[1]);
            
            answer = "LADICA";
            
            if(!chk[A]){
                chk[A] = true;
                union(A, B);
            }else if(!chk[B]){
                chk[B] = true;
                union(B, A);
            }else if(!chk[find(A)]){
                chk[find(A)] = true;
                union(A, B);
            }else if(!chk[find(B)]){
                chk[find(B)] = true;
                union(B, A);
            }else{
                answer = "SMECE";
            }
            
            bw.write(answer + "\n");
         }
         
         bw.flush();
     }
}