[백준] 18500번 미네랄2

문제 설명

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

문제 풀이

• 복잡한 시뮬레이션 문제이다.
• 풀이는 다음 과정으로 이뤄진다.

  1. 블록 제거
  2. 클러스터 생성
  3. 클러스터 떠있는지 판별 후 떨어뜨리기

• 클러스터 생성에는 BFS를 사용하였다.
• 클러스터가 떠있는지 판별하기 위해 맵을 순회하며 각 블록이 지면 및 다른 클러스터와 얼마나 떠있는지를 계산한다. (같은 클러스터와 거리는 무의미하다는 걸 주의)
• 이후 최소 거리만큼 특정 클러스터를 떨어뜨려주면 된다.

소스 코드 (JAVA)

import java.util.*;
import java.io.*;

public class Main {

    static class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static BufferedReader br;
    static BufferedWriter bw;

    static char[][] map;
    static int[][] chk;
    static int N, R, C, clusterIndex;
    static int[] arr;
    static int[] dx = {0,0,1,-1};
    static int[] dy = {1,-1,0,0};

    public static void solve() throws IOException {
        //막대기 던지기 왼쪽부터
        boolean isLeft = false;
        for (int n = 0; n < N; n++) {
            //1. 블럭 제거
            isLeft = !isLeft;
            destroyBlock(isLeft, arr[n]);
            //2. 클러스터 재구성
            makeCluster();
            //3. 클러스터 공중에 떠있는지 여부 확인 후 떨어뜨리기
            confirmFloatAndDropCluster();
        }
        //출력
        for (int i = 0; i < R; i++) {
            bw.write(map[i]);
            bw.write("\n");
        }
        bw.flush();
    }

    private static void confirmFloatAndDropCluster() {
        int[] minHeight = new int[clusterIndex + 1];  //클러스터 별 떠있는 최소 높이
        Arrays.fill(minHeight, Integer.MAX_VALUE);
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == '.') continue;
                //바닥과 맞닿아 있는 경우
                if (i + 1 == R) {
                    minHeight[chk[i][j]] = 0;
                    continue;
                }
                //같은 클러스터 위에 있는 경우
                if (chk[i+1][j] == chk[i][j]) continue;
                //공중에 떠있는 경우
                int diff = 0;
                while(true) {
                    int height = i + (++diff);
                    if (height == R) {
                        diff--;
                        break;
                    }

                    if (map[height][j] == '.')
                        continue;

                    if (chk[height][j] == chk[i][j]) {
                        diff = Integer.MAX_VALUE;
                        break;
                    }

                    if (chk[height][j] != chk[i][j]) {
                        diff--;
                        break;
                    }
                }
                minHeight[chk[i][j]] = Math.min(minHeight[chk[i][j]], diff);
            }
        }
        for (int i = 1; i <= clusterIndex; i++) {
            if (minHeight[i] == 0) continue;
            //떨어뜨리기
            for (int c = 0; c < C; c++) {
                for (int r = R-1; r >= 0; r--) {
                    if (chk[r][c] == i) {
                        chk[r][c] = 0;
                        chk[r + minHeight[i]][c] = i;
                        map[r][c] = '.';
                        map[r + minHeight[i]][c] = 'x';
                    }
                }
            }
            break;
        }
    }

    private static void makeCluster() {
        //초기화
        for (int i = 0; i < R; i++)
            Arrays.fill(chk[i], 0);
        clusterIndex = 0;     //클러스터 번호

        //클러스터 생성
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (map[i][j] == '.' || chk[i][j] != 0) continue;
                //클러스터 구성 시작
                clusterIndex++;
                Queue<Point> q = new ArrayDeque<>();
                q.add(new Point(i, j));
                chk[i][j] = clusterIndex;
                while(!q.isEmpty()) {
                    Point cur = q.poll();
                    for (int d = 0; d < 4; d++) {
                        int X = cur.x + dx[d];
                        int Y = cur.y + dy[d];
                        if (X < 0 || Y < 0 || X >= R || Y >= C) continue;
                        if (map[X][Y] == '.' || chk[X][Y] != 0) continue;
                        chk[X][Y] = clusterIndex;
                        q.add(new Point(X, Y));
                    }
                }
            }
        }
    }

    private static void destroyBlock(boolean isLeft, int height) {
        int ind = isLeft ? 0 : C-1;
        int diff = isLeft ? 1 : -1;
        while(map[height][ind] == '.') {
            ind += diff;
            if (ind < 0 || ind >= C)
                break;
        }
        if (ind >= 0 && ind < C)
            map[height][ind] = '.';
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];
        chk = new int[R][C];
        for (int i = 0; i < R; i++) {
            String input = br.readLine();
            for (int j = 0; j < C; j++)
                map[i][j] = input.charAt(j);
        }
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            arr[i] = R - arr[i];
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}

/*
- R x C
- N : 막대기 던진 횟수 (1 <= N <= 100)
- 왼쪽에서부터 던지기 시작함
- 클러스터는 공중에 떠있으면 동시에 떨어짐

R C
map
N
던지는 높이 배열 (N개)
 */