[백준] 2933번 / 18500번: 미네랄 1, 2 (JAVA)

문제 (GOLD 2)

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

18500번: 미네랄 2

---

풀이

시뮬레이션은 문제를 천천히 보면서 하나하나 구현하는게 가장 중요한 것 같다.

Logic

1. 높이 입력 받기
2. 던지는 위치에 따라 분기
3. 없어질 미네랄 위치 찾기 
4. 없어질 미네랄을 중심으로
   오른쪽 공격이면 상, 하, 좌
   왼쪽 공격이면  상, 하, 우 
   탐색하며, 떨어질 클러스터가 있는지 확인 ( breakMineral() )
   
   1. BFS 돌며, 바닥과 맞닿아 있는 곳이 있는지 확인
   2. 있으면 false 리턴, 없으면 true 리턴
   3. 탐색 시, broken 리스트에 클러스터들의 위치 저장
5. 클러스터 떨어뜨리기 ( fallMineral() )
   1. 떨어질 미네랄의 자리를 체크하지 않도록 임시 배열을 만들어 떨어질 미네랄 자리를 false 처리
   2. 모든 원소가 아래로 한칸 씩 떨어질 수 있는지 판별
   3. 떨어질 수 있다면, 기존의 미네랄 자리를 먼저 false로 모두 바꿔줌
      -> 나중에 겹칠 위험 있음 ㅠㅠ
   4. 새로운 미네랄 자리를 true 처리
   5. 한칸 아래로 내려간 인덱스로 다시 저장
   6. 떨어질 수 없을 때까지 반복

놓쳤던 부분

• 아래부분 체크!
  => 아래는 당연히 닿아있다고 생각해서 체크를 안했었음 ㅠㅠ
• 떨어뜨리기 전, 미네랄 자리 먼저 모두 false처리
  => 하나씩 돌며 false 바꾸고 true로 바로 바꾸는 로직을 했었지만, 자리가 겹칠 경우에 떨어진 미네랄 자리도 false처리 됨

코드

package simulation;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main_2933_미네랄 {
    static int[] di = {-1, 0, 1, 0};
    static int[] dj = {0, 1, 0, -1};
    static int R, C;
    static boolean[][] mineral;
    static int N;
    static List<int[]> broken;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        mineral = new boolean[R][C];
        for (int i = 0; i < R; i++) {
            String str = br.readLine();
            for (int j = 0; j < C; j++) {
                mineral[i][j] = (str.charAt(j) == '.') ? false : true;
            }
        }

        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int height = R-Integer.parseInt(st.nextToken());
            broken = new ArrayList<>();
            if(i%2==0){     // 왼쪽에서 공격
                int pos = 0;
                while(pos<C && !mineral[height][pos++]);            // 부실 미네랄의 j값 찾기
                if(pos >= C && !mineral[height][pos-1]) continue;
                mineral[height][--pos] = false;     // 부실 미네랄 false 처리
                if(pos < C-1 && height < R-1 && mineral[height][pos+1] && breakMineral(height, pos+1, height+1)) fallMineral();     // 오른쪽 탐색
                else if(pos < C && height > 0 && mineral[height-1][pos] &&breakMineral(height-1, pos, height)) fallMineral();   // 위쪽 탐색
                else if(pos < C && height < R-1 && mineral[height+1][pos] &&breakMineral(height+1, pos, height)) fallMineral(); // 아래쪽 탐색
            }
            else if(i%2 == 1){  // 오른쪽에서 공격
                int pos = C-1;
                while(pos>=0 && !mineral[height][pos--]);   // 부실 미네랄 j값 찾기
                if(pos < 0 && !mineral[height][pos+1]) continue;
                mineral[height][++pos] = false;
                if(pos > 0 && height < R-1 && mineral[height][pos-1] && breakMineral(height, pos-1, height+1)) fallMineral();   // 왼쪽 탐색
                else if(pos >= 0 && height > 0 && mineral[height-1][pos] && breakMineral(height-1, pos, height)) fallMineral(); // 위쪽 탐색
                else if(pos >= 0 && height < R-1 && mineral[height+1][pos] && breakMineral(height+1, pos, height)) fallMineral();   // 아래쪽 탐색
            }
        }

        for(int i =0 ; i < R ; i++){
            for(int j = 0 ; j < C ; j++){
                System.out.print((mineral[i][j])?'x':'.');
            }
            System.out.println();
        }
    }

    private static void fallMineral() {
        out:while(true) {
            boolean[][] tmpMin = new boolean[R][C];
            for(int i =0 ; i < R ; i++) tmpMin[i] = Arrays.copyOf(mineral[i], C);   // 떨어질 미네랄을 체크하지 않도록 임시 배열 만들어 줌
            for(int[] c : broken) tmpMin[c[0]][c[1]] = false;   // 떨어질 미네랄 자리를 false
            for(int[] c : broken) {
                if (c[0]+1 >= R || tmpMin[c[0]+1][c[1]]) {  // 모든 원소가 아래로 한칸씩 떨어질 수 있는지 판별
                    break out;
                }
            }
            // 한칸씩 떨어질 수 있다!
            for(int[] c : broken) mineral[c[0]][c[1]] = false;  // 기존의 미네랄 자리를 먼저 false 처리 -> 나중에 겹칠 위험 있음
            for(int i =0 ; i < broken.size() ; i++){
                int[] tmp = broken.get(i);
                mineral[tmp[0]+1][tmp[1]] = true;   // 새로운 자리 true
                broken.set(i, new int[]{tmp[0]+1, tmp[1]}); // 한칸 아래로 내려간 인덱스로 다시 저장
            }
        }
    }

    private static boolean breakMineral(int i, int j, int height) {
        boolean[][] visited = new boolean[R][C];
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{i, j});
        broken.add(new int[]{i, j});
        visited[i][j] = true;
        while(!q.isEmpty()){
            int[] cur = q.poll();
            for(int d= 0 ; d < 4 ; d++){
                int ni = cur[0]+di[d];
                int nj = cur[1]+dj[d];
                if(0<=ni&&ni<R && 0<=nj&&nj<C && mineral[ni][nj] && !visited[ni][nj]){
                    if(ni == R-1){      // 바닥과 맞닿아 있는 곳이 있으면 안 떨어지는 거임
                        broken.clear();
                        return false;
                    }
                    q.offer(new int[]{ni, nj});
                    visited[ni][nj] = true;
                    broken.add(new int[]{ni, nj});
                }
            }
        }
        return true;
    }
}