문제
BOJ 2933 : 미네랄 - https://www.acmicpc.net/problem/2933
풀이
전체적으로 봤을 때, 이루어지는 작업들은 다음과 같다.
- 주어진 높이와 방향의 미네랄 파괴
- 파괴된 시점에서 클러스터 중 공중에 떠있는 게 있는지 확인
- 있으면 내릴 수 있을 때까지 내리기
위와 같은 작업을 N번 반복하면 된다.
1번)의 경우 단순하게 높이와 방향만 맞춰 O -> .로 변경해주면 되기 때문에 크게 어렵지 않다.
2번)이 생각하기에 까다로웠는데, 공중에 떠있는지를 어떻게 판단해야 할 지 고민을 오래 했다. 결론은 '클러스터를 이루는 미네랄 중에 하나라도 바닥에 닿아있으면 공중에 떠있는게 아니다!'라는 것이다. 즉, 클러스터의 맨 아래 미네랄의 row 인덱스가 R-1이 아니라면 공중에 떠있는 상태라고 결론지을 수 있다.
클러스터를 알아내기 위해 BFS를 사용했다. 탐색 시 큐에 들어갔던 미네랄의 위치는 다시 ArrayList로 add하여 클러스터를 이루는 미네랄 정보를 저장해둔다. (필요 시 3번에서 사용)
클러스터를 이루는 미네랄 각각의 row 인덱스를 확인하여 최댓값(==가장 낮은 높이)을 알아낸다. 이 값이 R-1이 아닐 경우 공중에 떠있는 상태로 판단하고 3번 작업으로 넘어갔다.
문제에서 두 개 또는 그 이상의 클러스터가 동시에 떨어지는 경우는 없다 라고 명시했기 때문에 하나의 떠있는 클러스터를 발견하면 더 이상 보지 않고 return했다.
3번)에서는 몇 칸을 내릴 수 있는지를 먼저 판단해야했다. 우선 2번에서 저장해놓은 클러스터를 이루는 미네랄의 위치 정보를 사용해서 해당 위치들을 .으로 초기화했다.
그리고 한 칸씩 내려보며 바닥에 닿거나, 다른 미네랄과 닿을 경우 더 이상 내려갈 수 없다고 판단하여 내려갈 수 있는 칸 수 정보를 알아낸다.
이미 이 클러스터는 .로 초기화 해둔 상태이기 때문에 움직일 수 있는 칸 수(move) 만큼만 내려서 다시 x값을 넣어주기만 하면 된다. map[loc.i + move][loc.j] = 'x'; 와 같이 코드를 작성했다.
여기서 헤맸던 부분이 있는데, [바닥에 닿는다 or 다른 미네랄과 닿을 경우] 이 조건을 확인할 때 원래는 if문을 따로 작성하여 조건을 처리해주었다. 바닥에 닿는 경우면 move를 그대로 사용하고, 다른 미네랄과 닿는 경우면 move-1 해서(이미 닿았기 때문에 전 꺼로 적용) move만큼 내려주었다. 여기서 두 조건을 동시에 만족하는 예외케이스가 생긴다. 미네랄이 높이 1만큼만 있는 경우 한 칸씩 내리다 만났을 때 바닥에 닿음 + 다른 미네랄과 닿음 의 두 가지 경우를 모두 만족하게 되는데, 이럴 땐 미네랄과 닿음의 경우로 적용되어야 하지만 바닥에 닿음으로 적용되서 틀렸습니다가 나왔다. 그래서 조건을 같은 if문으로 묶어 OR문으로 처리하여 수정했다!
틀렸던 코드)
// 밑으로 한칸 내렸을 때 바닥과 닿으면
if (loc.i + move == R - 1) {
break outerLoop;
}
// or 밑으로 한칸 내렸을 때 다른 클러스터와 겹치면
if (map[loc.i + move][loc.j] == 'x') {
move--;
break outerLoop;
}위 예외케이스는 다음과 같은 반례로 확인할 수 있다.
4 4
...x
..xx
.xxx
xxxx
10
1 2 3 4 1 2 3 4 3 4코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static class Loc{
int i;
int j;
public Loc(int i, int j) {
this.i = i;
this.j = j;
}
}
static int R;
static int C;
static int N;
static char[][] map;
static int[][] clusters;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] inputs = br.readLine().split(" ");
R = Integer.parseInt(inputs[0]);
C = Integer.parseInt(inputs[1]);
map = new char[R][C];
for (int i = 0; i < R; i++) {
String tmp = br.readLine();
for (int j = 0; j < C; j++) {
map[i][j] = tmp.charAt(j);
}
}
N = Integer.parseInt(br.readLine());
inputs = br.readLine().split(" ");
for (int i = 0; i < N; i++) {
int bar = Integer.parseInt(inputs[i]);
destructMineral(bar, i%2==0?1:2);
setCluster();
}
// print result
for (int i = 0; i < R; i++) {
System.out.println(map[i]);
}
}
public static void destructMineral(int height, int direction){ // d : 1이면 왼쪽, 2면 오른쪽에서
if(direction==1) {
for (int col = 0; col < C; col++) {
if(map[R-height][col]=='x'){
map[R-height][col]='.';
return;
}
}
}else{
for (int col = C - 1; col >= 0; col--) {
if(map[R-height][col]=='x'){
map[R-height][col]='.';
return;
}
}
}
// R이 8인데 높이 1을 부시려면 i 7을 봐야함
// 8-1=7
// 8-2=6
// ...
// 8-8=0
}
public static void setCluster(){
clusters = new int[R][C]; // 전부 0으로 초기화 되어있음
int cluster_num = 1;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if(map[i][j]=='x' && clusters[i][j]==0){
if(findCluster(i,j, cluster_num)){ // 떠있는 클러스터를 발견하면
return;
}
cluster_num++;
}
}
}
}
public static boolean findCluster(int i, int j, int cluster_num){
int[] mi = {0, 0, -1, 1};
int[] mj = {1, -1, 0, 0};
int lowest = -1;
Queue<Loc> q = new LinkedList<>();
ArrayList<Loc> arr = new ArrayList<>();
q.add(new Loc(i, j));
clusters[i][j] = cluster_num;
while (!q.isEmpty()) {
Loc now = q.poll();
lowest = Math.max(lowest, now.i);
for (int d = 0; d < 4; d++) {
int ni = now.i + mi[d];
int nj = now.j + mj[d];
if (ni < 0 || nj < 0 || ni >= R || nj >= C) continue;
if (clusters[ni][nj]==0 && map[ni][nj]=='x') {
clusters[ni][nj] = cluster_num;
q.add(new Loc(ni, nj));
}
}
arr.add(now);
}
// 클러스터의 가장 아래가 바닥과 맞닿아있지 않으면 = 공중에 떠있으면!
// 떨어지는 클러스터는 오직 하나만 있음!
if(lowest!=R-1){
moveCluster(arr);
return true;
}
return false;
}
public static void moveCluster(ArrayList<Loc> arr){
int move = 1;
for (Loc loc : arr) { // 원래꺼 다 지우고
map[loc.i][loc.j] = '.';
}
outerLoop:
while(true){
for (Loc loc : arr) {
// 밑으로 한칸 내렸을 때 바닥을 넘어가면
// or 밑으로 한칸 내렸을 때 다른 클러스터와 겹치면
// ==>그 전까지만 내릴 수 있음
if (loc.i + move == R || map[loc.i + move][loc.j] == 'x') {
move--;
break outerLoop;
}
}
move++;
}
for (Loc loc : arr) { // 새로 업데이트
map[loc.i + move][loc.j] = 'x';
}
}
}
정리
✔ 알고리즘 분류 - 구현, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시뮬레이션
✔ 난이도 - 🟡 Gold 2🤦♀️ 오늘의 메모
- 오랜만에 어려운 시뮬레이션 문제를 풀었던 것 같다. 조건이 엄청 많은 건 아니었는데 문제를 이해하는 데에 시간이 오래 걸렸고, 반례를 다 통과하는데도 틀렸습니다가 떠서 많이 헤맸다.. 오늘의 교훈은 맞는 것 같은 조건도 두들겨보기,,, 정말 저 조건처리에서 실수가 있을 줄은 생각지도 못했다.
(앞으로 안틀리면 되지!)
참고 사이트
https://velog.io/@hyeon930/BOJ-2933-%EB%AF%B8%EB%84%A4%EB%9E%84-Java
