BOJ G1 2933 미네랄 JAVA

2933번: 미네랄

---

문제 읽기

이 문제는 처음 읽었을 때 시뮬레이션 문제인 것 같았다. R, C, N의 값도 그리 크지 않고 시뮬레이션을 했을 때 말고는.. 딱히 답을 구할 방법이 생각나진 않았다.

 

그래서 다음과 같이 초기 계획을 세웠다.

거의 이 계획대로 코드를 작성했다.

(빨간색으로 N-1행이라 되어있는데 R-1행이다. 오타이다.)

---

문제 풀기

문제 풀이 과정을 다시 한 번 정리해보겠다.

우선 문제를 풀 때 특별한 알고리즘은 사용하지 않았고, BFS와 Queue, 그리고 작은 꼼수(?)가 필요하다

1. 막대를 던진다
   1. 던진 높이에 대해 미네랄을 만났다면
      1. 미네랄을 파괴한다.
      2. 바닥과 접해있는 미네랄과, 떠 있는 미네랄을 visited 배열을 사용해 구분한다.
         1. R-1행(바닥과 접해있는 층)을 다 보면서 미네랄이 존재하면 BFS를 돌며 방문 체크한다. (방문했다 == 바닥과 접해있는, 떠 있지 않은 미네랄 클러스터)
         2. 그 다음 R-2행부터 0행까지 보면서, 방문하지 않은, 즉 떠 있는 미네랄을 찾는다
            1. 없으면 continue
            2. 있으면 떠 있는 미네랄부터 행을 증가시키며 얼마나 내릴 수 있는지 diff를 구한다.
               1. 이때, 미네랄 클러스터의 바닥면에 해당하는 칸만 유효하다. 내부 칸은 쓸모가 없다.

               2. 

            3. 떠 있는 미네랄 클러스터에 포함되는 모든 점을 bfs를 활용해 찾고, 큐와 반복문을 이용해 중력을 적용한다.

---

실수한 부분

아래는 문제의 조건이다.

처음에 위 글을 보고 착각한 점이 있다. 떠 있는 클러스터에서, 무조건 가장 아래에 있는 행이 바닥 또는 미네랄 위에 닿는 경우만 주어진다고 착각해서 이 부분 때문에 4%에서 계속 틀렸었다. 도저히 모르겠어서 질문 게시판을 봤더니 이거에 대한 얘기가 있었고, 이 부분을 고치니 정답!

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_G1_2933_미네랄 {
    static class Pos{
        int r, c;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    static int R, C;
    static char[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(in.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        for (int i = 0; i < R; i++) {
            map[i] = in.readLine().toCharArray();
        }

        int N = Integer.parseInt(in.readLine());
        st = new StringTokenizer(in.readLine());
        int dir = 0;
        while (N-- > 0) {
            int h = Integer.parseInt(st.nextToken()); //던진 높이

            //미네랄 파괴
            if (breakMineral(dir, h)) {
                //파괴했으면 붕 뜬 미네랄 있는지 체크
                boolean[][] visited = new boolean[R][C];

                //우선 바닥에 붙어있는 미네랄 체크
                for (int j = 0; j < C; j++) {
                    if (!visited[R - 1][j] && map[R - 1][j] == 'x') bfs(R - 1, j, visited);
                }

                int minDiff = Integer.MAX_VALUE;
                int targetI = 0;
                int targetJ = 0;
                for (int i = R - 2; i >= 0; i--) {
                    //나머지 중에서 미네랄 있는데 visited가 false이면 떠있는 것 - only one(문제 조건)
                    for (int j = 0; j < C; j++){
                        if (map[i][j] == 'x' && !visited[i][j]){ //클러스터의 아래 둘레만!!!
                            ///떠 있다. 얼마나 떠 있는지 확인
                            int diff = 0;
                            for (int k = i+1; k < R; k++){
                                if (map[k][j] == 'x' && visited[k][j]) break;
                                diff++;
                            }
                            if (minDiff > diff){
                                minDiff = diff;
                                targetI = i;
                                targetJ = j;
                            }
                        }
                    }
                }
                if (minDiff != Integer.MAX_VALUE) {
                    //해당 클러스터를 모두 diff만큼 내려준다.
                    downCluster(new Pos(targetI, targetJ), minDiff);
                }
            }
            dir++;
        }

        //출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < R; i++){
            for (int j = 0; j < C; j++){
                sb.append(map[i][j]);
            }
            sb.append("\\n");
        }
        System.out.println(sb);
    }

    private static void downCluster(Pos pos, int diff) {
        //해당 점부터 bfs -> 클러스터 점들을 모두 큐에 담는다.
        //큐를 돌면서 (i, j)의 x를 지우고 .을 넣는다. 이거 그냥 bfs랑 같이 해도 되긴 한데.. 일단 분리
        //큐를 돌면서 (i+diff, j)에 x를 넣는다.

        Queue<Pos> cluster = new ArrayDeque<>(); //점을 모을 클러스터

        //bfs
        Queue<Pos> q = new ArrayDeque<>();
        q.offer(pos);
        cluster.offer(pos);
        boolean[][] visited = new boolean[R][C];
        visited[pos.r][pos.c] = true;

        while(!q.isEmpty()){
            Pos cur = q.poll();

            for (int di = 0; di < 4; di++){
                int nr = cur.r + dr[di];
                int nc = cur.c + dc[di];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc] || map[nr][nc] == '.') continue;

                visited[nr][nc] = true;
                q.offer(new Pos(nr, nc));
                cluster.offer(new Pos(nr, nc));
            }
        }

        //x 지우기
        for (Pos p : cluster){
            map[p.r][p.c] = '.';
        }
        //x 내리기
        for (Pos p : cluster){
            map[p.r + diff][p.c] = 'x';
        }
    }

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    private static void bfs(int i, int j, boolean[][] visited) {
        Queue<Pos> q = new ArrayDeque<>();
        q.offer(new Pos(i, j));
        visited[i][j] = true;

        while(!q.isEmpty()){
            Pos cur = q.poll();

            for (int di = 0; di < 4; di++){
                int nr = cur.r + dr[di];
                int nc = cur.c + dc[di];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc] || map[nr][nc] == '.') continue;

                visited[nr][nc] = true;
                q.offer(new Pos(nr, nc));
            }
        }
    }

    private static boolean breakMineral(int dir, int h) {
        boolean isBroken = false;
        if (dir % 2 == 0) {
            //왼 -> 오
            for (int j = 0; j < C; j++){
                if (map[R-h][j] == 'x') {
                    map[R-h][j] = '.'; //파괴
                    isBroken = true;
                    break;
                }
            }
        }
        else{
            //오 -> 왼
            for (int j = C-1; j >= 0; j--){
                if (map[R-h][j] == 'x') {
                    map[R-h][j] = '.'; //파괴
                    isBroken = true;
                    break;
                }
            }
        }
//        System.out.println("isBroken " + isBroken);
        return isBroken;
    }
}