백준 : 2933 JAVA

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

2933번: 미네랄

BFS DFS 카테고리에 잇엇지만 사실상 시뮬레이션 문제.

명령의 순서쌍을 0 1 2 3 4 5  총 6개라고할때 k%2 == 0 이면 왼쪽에서 던지는거 아닐시 오른쪽에서 던지는 것이라고 판단한다.

그렇게 던젓을때 처음으로 'x' 라고 나오는 좌표를 x y 라고할때 그좌표를 '.' 으로 바꿔준다.

그리고 그좌표를기준으로 상하좌우 를 BFS탐색한다. BFS를 탐색하면서 새로운 배열에 좌표값을 넣고 

Queue 에서 poll 시 좌표를 '.' 해준다. 이렇게하면 하나의 구역을 .처리하고 그좌표값들을 배열에 저장한다.

이제 배열에 담김 좌표값을 얼마나 내릴수 있는 지확인한다. 이때방법은 모든 배열을 탐색하면서 y-1 에 x가 잇거나 OutofIndexing일 경우 down 을 멈춘다. down 초기값은 0이고 하나의 반복이 돌때마다 down을 올려주면서 검사한다. 

특정 down에서 더이상 내리지못할때 map[i-down][j] = 'x' 다시 그려준다.

이반복을 매 쿼리마다 실행하면 시뮬레이션이 완성된다.
문제에서는 나의 미네랄이 부서젓을때 동시에 내려가는 것은 없다고햇다 따라서 내려간에가 하나라도 나오면 사방탐색을 종료하고 내려가도된다.

package day0303;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class B2933 {
    static int N,M;
    static char map[][];
    static int K;
    static int[] doit;
    static int[]dy = {1,0,0,-1};
    static int[]dx = {0,-1,1,0};
    static class Pair{
        int y;
        int x;
        public Pair(int y, int x) {
            super();
            this.y = y;
            this.x = x;
        }
    }
    
    
    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());
        map = new char[N+1][M+1];
        Pair[] move = new Pair[N*M+1];
        for(int i=N;i>=1;i--) {
            String str = br.readLine();
            for(int j=1;j<=M;j++) {
                
                map[i][j] = str.charAt(j-1);
            }
        }
        
        K = Integer.parseInt(br.readLine());
        doit = new int[K];
        st = new StringTokenizer(br.readLine());
        //짝수이면 왼쪽에서 던진거
        for(int k=0;k<K;k++) {
            doit[k] = Integer.parseInt(st.nextToken());
        }
        
        
        int y=0;
        int x=0;
        
        for(int k=0;k<K;k++) {
            if(k%2==0) {
                for(int j=1;j<=M;j++) {
                    if(map[doit[k]][j]=='x') {
                        map[doit[k]][j] ='.';
                        y=doit[k];
                        x=j;
                        break;
                    }
                }
            }else {
                for(int j=M;j>=1;j--) {
                    if(map[doit[k]][j]=='x') {
                        map[doit[k]][j] ='.';
                        y=doit[k];
                        x=j;
                        break;
                    }
                }
            }
            
            for(int d=0;d<4;d++) {
                int ny = y+dy[d];
                int nx = x+dx[d];
                if(ny<1||nx<1||ny>N||nx>M)continue;
                if(map[ny][nx]=='.')continue;
                
                int ms =0;
                Queue<Pair> q = new LinkedList<>();
                map[ny][nx] ='.';
                q.add(new Pair(ny, nx));
                while(!q.isEmpty()) {
                    Pair tmp = q.poll();
                    move[ms++] = tmp;
                    
                    for(int dd=0;dd<4;dd++) {
                        ny = tmp.y +dy[dd];
                        nx = tmp.x +dx[dd];
                        if(ny<1||nx<1||ny>N||nx>M)continue;
                        if(map[ny][nx]=='.')continue;
                        map[ny][nx] ='.';
                        q.add(new Pair(ny, nx));
                    }
                }
 
                //끝나고나면 move에  < ms-1 까지 미네랄의 위치정보가 있다
                //이거가지고 밑에 아무것도 없을때까지 조사하면됨
                //얼마나 밑으로 내릴 수 
                int down = 0;
                boolean escap = false;
                while(true) {
                    for(int m=0;m<ms;m++) {
                        ny = move[m].y;
                        nx = move[m].x;
                        
                        if( ny-down-1<1||map[ny-down-1][nx] =='x') {
                            escap = true;
                            break;
                        }
                    }
                    if(escap)break;
                    down++;
                }
                
                for(int m=0;m<ms;m++) {
                    ny = move[m].y;
                    nx = move[m].x;
                    map[ny-down][nx] ='x';
                }
            }
            
        }
        
        StringBuilder sb = new StringBuilder();
        for(int i=N;i>=1;i--) {
            for(int j=1;j<=M;j++) {
                sb.append(map[i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }
}