[백준 2933] 미네랄

 

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

2933번: 미네랄

 

막대기를 던질 때마다 미네랄 파괴에 의한 클러스터의 분리를 확인하고, 

분리된 클러스터가 있으면 클러스터는 중력에 의하여 떨어지고,  떨어진 후에 다음 막대기를 던지는 것을 반복함.

 

체크할 것..

1) 같은 클러스터를 "탐색"

2) 클러스터가 떨어지는지 확인. 떨어진다면 어디에 떨어지는지

 

일단 1)에 대하여는 dfs를 통하여 같은 클러스터의 범위를 확인했다.

그 다음 클러스터를 확장해 나가면서, 바닥과 맞닿아 있는지를 확인했다(2))

확인 후 바닥과 맞닿아 있을 때 해당 클러스터에 대한 탐색을 종료했다(떨어지지 않는 클러스터이므로..)

탐색 종료 후 바닥과 맞닿아 있지 않다고 판단되었을 때, 

떨어지는 높이를 계산해야 했고 이를 drow통하여 해결했다.

 

 

 

그리고 주의해야 했던 점

1) 파괴된 미네랄의 아래뿐만 아니라 위 또한 조사해야 함

 

ex)

. x x x
. x . x
. x . x
. x . .
. x . .

위의 경우 처음 막대기의 높이가 4일 때.. 위쪽의 클러스터가 떨어질 수 있음

 

2) 떨어질 때 무조건 바닥까지 떨어지는 게 아니라, 다른 클러스터 위로 떨어져 합체될 수 있기 때문에 

떨어지는 높이(drow)를 1씩 증가시키면서 어느 위치에 떨어지는지를 확인해야 함.

 

 

 

 

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Main {
    static int R,C;
    static boolean cFlag;
    static char[][] map;
    static boolean[][] isVisited;
    static ArrayList<Coord> cluster;
    static final int dx[] = {0, 0, -1, 1};
    static final int dy[] = {1, -1, 0, 0};
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String line = br.readLine();

        R = Integer.valueOf(line.split(" ")[0]);
        C = Integer.valueOf(line.split(" ")[1]);

        map = new char[R][C];
        isVisited = new boolean[R][C];

        //input
        for (int i = 0; i < R; i++) {
            line = br.readLine();
            map[i] = line.toCharArray();
        }

        int count = Integer.valueOf(br.readLine());
        int[] heights = new int[count];
        heights = Arrays.stream(br.readLine().split(" "))
                .mapToInt(Integer::parseInt).toArray();
        int h;
        cluster = new ArrayList<Coord>();
        for (int i = 0; i < count; i++) {
            h = heights[i];
            int row = R - h;
            String str = String.valueOf(map[row]);
            int index = (i % 2 == 0) ? str.indexOf("x") : str.lastIndexOf("x");
            if(index==-1)   continue;
            map[row][index] = '.';
            //
            for (int j = 0; j < 4; j++) {
                int nx = row + dx[j];
                int ny = index + dy[j];
                if(nx>R-1 || nx<0 || ny>C-1 || ny<0) continue;  //outofindex
                if (map[nx][ny] == 'x' && isVisited[nx][ny]==false) {
                    cFlag=true;
                    dfs(nx, ny);
                    if (!cluster.isEmpty()) {
                        down();
                        cluster.clear();
                        isVisited=new boolean[R][C];
                        break;
                    }
                }
            }
            isVisited=new boolean[R][C];
        }

        //map print
        for (int row = 0; row < R; row++) {
            bw.write(String.valueOf(map[row]) + "\n");
        }

        bw.flush();
        bw.close();
    }

    private static void dfs(int row, int col) {
        if (row == R - 1) {
            cluster.clear();
            cFlag = false;
            return;
        }
        if(cFlag)   cluster.add(new Coord(row, col));
        isVisited[row][col]=true;
        //right, left, up, down
        for (int i = 0; i < 4; i++) {
            int nx = row + dx[i];
            int ny = col + dy[i];
            if(nx>R-1 || nx<0 || ny>C-1 || ny<0) continue;  //outofindex
            if (!isVisited[nx][ny] && map[nx][ny]=='x') {
                dfs(nx, ny);
            }
        }
    }

    private static void down() {
        for (Coord c : cluster) map[c.row][c.col] = '.';

        int drow = 0;
        boolean flag=true;
        while (flag) {
            drow++;
            for (Coord c : cluster) {
                if (c.row + drow == R || map[c.row + drow][c.col] == 'x') {
                    drow--;
                    flag = false;
                    break;
                }
            }
        }
        for(Coord c:cluster) map[c.row + drow][c.col] = 'x';

    }

}

class Coord {
    int row;
    int col;

    public Coord(int row, int col) {
        this.row = row;
        this.col = col;
    }
}