알고리즘39 :: BOJ_2933_미네랄

package backjun;
 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
 
class Pair4{
    int first, second;
    Pair4(int first, int second){
        this.first = first;
        this.second = second;
    }
}
public class mineral {
 
    private static int n,m;
    private static char[][] a;
    private static boolean[][] c;
    private static int[] dx = {-1,1,0,0};
    private static int[] dy = {0,0,-1,1};
    private static ArrayList<Pair4> list = new ArrayList<>();
    private static void dfs(int x, int y) {
        if(a[x][y]=='.') return ;
        if(c[x][y]) return ; 
        c[x][y] = true;
        list.add(new Pair4(x,y));
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0<=nx && nx<n && 0<=ny && ny<m) {        
                dfs(nx,ny);
            }
        }
    }
    private static void simulate() {
        for(int i=0; i<n; i++)
            Arrays.fill(c[i], false);
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(a[i][j] == '.') continue;
                if(c[i][j]) continue;
                list.clear();
                dfs(i,j);
                int[] low = new int[m];
                Arrays.fill(low, -1);
                for(Pair4 p: list) {
                    low[p.second] = Math.max(low[p.second], p.first);
                    a[p.first][p.second] = '.';
                }
                int lowest = n;
                for(int x,y=0; y<m; y++) {
                    if(low[y]==-1)continue;
                    for(x=low[y]; x<n && a[x][y]=='.'; x++);
                    lowest = Math.min(lowest, x-low[y]-1);
                }
                for(Pair4 p : list) {
                    p.first+=lowest;
                    a[p.first][p.second]='x';
                    c[p.first][p.second]=true;
                }
                
            }
        }
    }//이 코드에서 궁금한것은 지우고 내리는 데 일부 x가 내려가다 x를 만나는 경우 못내려가야 하는데 내려갈수도 있지 않나요?
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        a = new char[n][];
        c = new boolean[n][m];
        for(int i=0; i<n; i++) {
            a[i] = sc.next().toCharArray();
        }//
        
        int k = sc.nextInt();
        for(int i=0; i<k; i++) {
            //첫 번째 막대는 왼쪽에서 오른쪽으로 던졌으며, 두 번째는 오른쪽에서 왼쪽으로, 이와 같은 식으로 번갈아가며 던진다.
            int height = n - sc.nextInt();
            if(i%2!=0) {
                //오른쪽 ->왼쪽
                for(int j=m-1; j>=0; j--) {
                    if(a[height][j]=='x') {
                        a[height][j] = '.';
                        break;
                    }
                }
            }else {
                //왼쪽->오른쪽
                for(int j=0; j<m; j++) {
                    if(a[height][j]=='x') {
                        a[height][j] = '.';
                        break;
                    }
                }
            }
            simulate();
        }
        for(int i=0; i<n; i++)
            System.out.println(a[i]);
    }
 
}
 

1. 미네랄을 왼쪽, 오른쪽 입력 값에 따라 순서대로 지워준다. 

2. DFS로 클러스터링 한다.

3. 클러스터링한 좌표값에서 맨 밑바닥과 차이가 제일 작은(==lowest) 높이를 찾아서 업데이트한다.