문제
은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다.
은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대해서 다음과 같은 과정을 거친다.
- 서랍 Ai가 비어있다면, i번 술을 그 서랍에 보관한다.
- 서랍 Bi가 비어있다면, i번 술을 그 서랍에 보관한다.
- Ai에 들어있는 술을 다른 서랍으로 이동시킨다.(다른 서랍은 Ai에 들어있는 술이 들어갈 수 있는 서랍 중 하나이다) 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Ai에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
- Bi에 들어있는 술을 다른 서랍으로 이동시킨다. 만약, 그 서랍에도 이미 술이 들어있다면, 그 술을 다른 서랍으로 이동시킨다. 이런 과정을 거쳐서 빈 서랍을 하나 찾아 술을 모두 이동할 수 있는 경우에는, 술을 이동시키고 i번 술을 Bi에 보관한다. 불가능한 경우에는 다음 규칙으로 넘어간다.
- 위의 과정이 모두 불가능한 경우에는 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");
}
}
'자료구조 공부 > Union-Find' 카테고리의 다른 글
[백준] 1043 거짓말 (0) | 2021.08.22 |
---|---|
백준 3780 (네트워크 연결) (0) | 2021.02.11 |
백준 10775 (공항) (0) | 2021.02.07 |
백준 4195 (친구 네트워크) (0) | 2021.02.04 |
백준 1717 (집합의 표현) (0) | 2021.02.03 |