#백준_2933 미네랄 - Java 자바

# 유형 : 시뮬레이션 + 탐색(BFS,DFS)

# 난이도 : 골드 3

# 구현+탐색 문제라서 문제가 어렵기 보다는 코딩하기 좀 복잡했다. 미네랄을 파괴할 때마다 파괴된 미네랄의 4방향 중에 존재하는 클러스터를 탐색(BFS 또는 DFS)로 찾고 각 클러스터에 속하는 부분 원소가 한개라도 바닥에 닿지 않았다면 내리는 작업을 해주면 된다. 문제의 핵심은 클러스터 부분 원소중 한개라도 바닥에 닿을때까지 조건을 따지며 내려주면 된다는 것.

package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2933 {
    static boolean check = false;
    static ArrayList<Point> cluster = new ArrayList<>();
    static int moveX[] = {0, -1, 0, 1};
    static int moveY[] = {-1, 0, 1, 0};
    static int R,C,N;
    static char arr[][];
    static boolean visit[][];
    static int height[];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new char[R][C];
        visit = new boolean[R][C];
        for(int r=0; r<R; r++) {
            String str = br.readLine();
            for(int c=0; c<C; c++) {
                arr[r][c] = str.charAt(c);
            }
        }
        N = Integer.parseInt(br.readLine());
        height = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int n=1; n<=N; n++) {
            height[n] = Integer.parseInt(st.nextToken());
            
            boolean left = true;
            int x=-1, y=0;
            
            if(n%2 == 0)
                left = false;
            
            y = R - height[n];
            
            if(left) {
                for(int c=0; c<C; c++) {
                    if(arr[y][c] == 'x') {
                        x = c;
                        break;
                    }
                }
            }else {
                for(int c=C-1; c>=0; c--) {
                    if(arr[y][c] == 'x') {
                        x = c;
                        break;
                    }
                }
            }
            
            if(x == -1)
                continue;
            
            arr[y][x] = '.';
            
            for(int d=0; d<4; d++) {
                int newY = y + moveY[d];
                int newX = x + moveX[d];
                
                if(0<=newY && newY<R && 0<=newX && newX<C && arr[newY][newX] == 'x') {
                    cluster = new ArrayList<>();
                    check = false;
                    visit = new boolean[R][C];
                    
                    cluster.add(new Point(newX, newY));
                    
                    bfs(newY, newX);
                    
                    if(check)
                        continue;
                    
                    while(true) {
                        boolean isPossible = true;
                        
                        for(int i=0; i<cluster.size(); i++) {
                            Point po = cluster.get(i);
                            arr[po.y][po.x] = '.';
                        }
                        for(int i=0; i<cluster.size(); i++) {
                            Point po = cluster.get(i);
                            int nextY = po.y + 1;
                            
                            if(nextY == R || arr[nextY][po.x] == 'x') {
                                isPossible = false;
                                break;
                            }
                        }
                        
                        for(int i=0; i<cluster.size(); i++) {
                            if(isPossible)
                                cluster.get(i).y++;
                            arr[cluster.get(i).y][cluster.get(i).x]='x';
                        }
                        if(!isPossible)
                            break;
                        
                    }
                }
            }
        }
        
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                System.out.print(arr[i][j]);
            }System.out.println();
        }
    }
    
    private static void bfs(int y, int x) {
        // TODO Auto-generated method stub
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        visit[y][x] = true;
        while(!queue.isEmpty()) {
            Point po = queue.poll();
            if(po.y == R-1) {
                check = true;
                return;
            }
            
            for(int d=0; d<4; d++) {
                int newY = po.y + moveY[d];
                int newX = po.x + moveX[d];
                
                if(0<=newY && newY<R && 0<=newX && newX<C && !visit[newY][newX] && arr[newY][newX]=='x') {
                    visit[newY][newX] = true;
                    cluster.add(new Point(newX,newY));
                    queue.add(new Point(newX,newY));
                }
            }
        }
    }
    
}