백준 9938 (방 청소)

문제

---

은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다.  서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다.

은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대해서 다음과 같은 과정을 거친다.

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

각각의 술에 대해서, 서랍에 보관할 수 있는지, 그 자리에서 마셔버리는지를 구하는 프로그램을 작성하시오.

 

 

풀이

---

결국 이문제의 핵심은 현재의 번호의 서랍에 술이 들어있나 안들어 있나다.

술이 들어간 서랍의 번호에는 술이 들어있다고 표시를 해준다.

 

● 1번 조건

    Union 함수를 통해 a 의 루트가 b 의 루트가 되면 된다.  

visited[a] = true;
union(a, b);

 

● 2번 조건

    1번 조건과 반대로 b 의 루트가 a의 루트가 되면 된다.

visited[b] = true;
union(b, a);

 

● 3번 조건

    a 의 루트가 비어있다면 하나씩 자리를 바꿔주면 모두다 술을 넣을 수 있다.

    하지만, a 의 루트가 b 의 루트가 되면 된다. 굳이 바뀐 자리를 신경안써도 된다.

    전체적으로 그 서랍이 채워져있는지가 중요 하다.

if(!visited[find(drawer[a])]) {
	visited[find(drawer[a])] = true;
	union(a, b);
}

 

● 4번 조건

    3번 조건과 반대로 조건을 주면 된다.

if(!visited[find(drawer[b])]) {
	visited[find(drawer[b])] = true;
	union(b, a);
}

 

이 위의 모든 조건이 만족하지 않는다면 

"SMECE" 를 출력시켜주면 된다.

 

<전체 코드>

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

public class Main {	
	
	static StringBuilder sb = new StringBuilder();

	static int[] drawer;
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
		int n = Integer.parseInt(st.nextToken());
		int l = Integer.parseInt(st.nextToken());
		
		drawer = new int[l + 1];
		visited = new boolean[l + 1];
		for(int i = 1 ; i <= l ; i++) {
			drawer[i] = i;
		}
		
		for(int i = 0 ; i < n ; i++) {
			st = new StringTokenizer(bufferedReader.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(!visited[a]) {
				visited[a] = true;
				union(a, b);
			}
			else if(!visited[b]) {
				visited[b] = true;
				union(b, a);
			}
			else if(!visited[find(drawer[a])]) {
				visited[find(drawer[a])] = true;
				union(a, b);
			}
			else if(!visited[find(drawer[b])]) {
				visited[find(drawer[b])] = true;
				union(b, a);
			}
			else {
				sb.append("SMECE\n");
			}
			
		}
		
		System.out.println(sb);
	}
	
	static int find(int x) {
		
		if(x == drawer[x])
			return x;
		else
			return drawer[x] = find(drawer[x]);
	}
	
	static void union(int a, int b) {
		
		a = find(a);
		b = find(b);
		
		drawer[a] = b;
		sb.append("LADICA\n");
	}
}