(백준) 미네랄 _ 18500 [java]

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

 

🐢 설명

왼쪽, 오른쪽에서 던지는 돌에 미네랄이 깨지고, 깨진 미네랄이 바닥과 연결되어 있지 않다면 땅으로 떨어져야 한다. 이때 미네랄은 바닥과 붙어있는 미네랄과 닿을때까지 or 바닥에 닿을 때까지 떨어진다.

 

로직은 간단하다.

1. 왼쪽 오른쪽 번갈아 가면서 돌을 던진다.
2. 돌을 던져서 방향대로 가다가 해당 높이에서 만나는 첫 미네랄을 부순다.
3. (맨밑) 바닥에서 미네랄을 탐색한다. 탐색 된 미네랄들은 전부 바닥과 연결된 미네랄들이다.
4. 맨위 부터 탐색되지 않은 미네랄을 찾는다. 탐색되지 않은 미네랄은 미네랄이 부셔지면서 공중에 뜬 미네랄이다.
5. 탐색되지 않은 미네랄 덩어리는 하나라고 문제에 나와있으므로 전부 하나의 리스트에 담아준다.
6. 리스트에 있는 미네랄 조각들에 대해서 떨어질 수 있는 최대 높이의 최소값을 구해준다. (한 덩어리이므로 최소높이만큼 같이 떨어진다)
7. 구한 높이만큼 이동시켜준다.

 

🐢코드

//package Gold이상문제_정리;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static int N, M, T;
    static char[][] board;
    static boolean[][] mark;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};
    static int[] turn;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new char[N+1][M+1];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                board[i][j] = s.charAt(j);
            }
        }

        T = Integer.parseInt(br.readLine());
        turn = new int[T];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < T; i++) {
            turn[i] = Integer.parseInt(st.nextToken());
        }

        shot();
        printMineral();
    }

    private static void shot() {
        int t = 0;
        for (int y : turn) {
            destroy(N - y, t++ % 2 == 0);
            checkIsFall();
        }
    }

    private static void printMineral() {
        StringBuilder answer = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                answer.append(board[i][j]);
            }
            answer.append("\n");
        }
        System.out.print(answer);
    }

    private static void checkIsFall() {
        mark = new boolean[N][M];
        makringFirst();
        moveNotMarked();
    }

    private static void moveNotMarked() {
        ArrayList<int[]> lists = new ArrayList<>();

        for (int y = 0; y < N; y++) {
            for (int x = 0; x < M; x++) {
                if (board[y][x] == 'x' && !mark[y][x]) {
                    board[y][x] = '.';
                    lists.add(new int[]{y, x});
                }
            }
        }

        int height = 101;
        for (int[] dot : lists) {
            int y = dot[0];
            int x = dot[1];

            while (y < N) {
                if (!mark[y][x] && board[y][x] == 'x') break;
                if (mark[y][x] && board[y][x] == 'x') {
                    height = Math.min(height, y - dot[0]);
                    break;
                }
                if (y == N - 1) {
                    height = Math.min(height, N - dot[0]);
                    break;
                }
                y++;
            }
        }

        for (int[] dot : lists) {
            int y = dot[0];
            int x = dot[1];
            board[y + height - 1][x] = 'x';
        }
    }

    private static void makringFirst() {
        for (int x = 0; x < M; x++) {
            if (!mark[N - 1][x] && board[N - 1][x] == 'x') {
                dfs(N - 1, x);
            }
        }
    }

    private static void dfs(int y, int x) {
        if (mark[y][x]) return;

        mark[y][x] = true;

        for (int d = 0; d < 4; d++) {
            int ny = dy[d] + y;
            int nx = dx[d] + x;

            if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
            if (board[ny][nx] == '.') continue;
            if (mark[ny][nx]) continue;
            dfs(ny, nx);
        }
    }

    private static void destroy(int y, boolean left) {
        if (left) {
            for (int x = 0; x < M; x++) {
                if (board[y][x] == 'x') {
                    board[y][x] = '.';
                    break;
                }
            }
        } else {
            for (int x = M - 1; x >= 0; x--) {
                if (board[y][x] == 'x') {
                    board[y][x] = '.';
                    break;
                }
            }
        }
    }
}

🐢 마무리