BOJ - 2933 ) 미네랄

 

---

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

2933번: 미네랄

---

미네랄 동굴에서 창영과 상근이 반대편으로 창을 던지면서 미네랄이 깨지는 것을 구현하면서 

 

깨진 덩어리들이 공중에 떠있으면은 바닥으로 내리고, 덩어리가 바닥과 연결되어있으면 다음 명령으로 진행하는

 

탐색&시뮬문제이다.

 

알고리즘은 다음과 같다.

 

1 ) 입력에따라서 해당줄에 홀수번째는 좌에서 우, 짝수번째는 우에서 좌로 창을던져 제일먼저 만나는 미네랄을 부순다.

 

2 ) 처음에 바닥과 연결되어있는 클러스터를 찾기위해서 r-1행에서 bfs를 실행시켜준다.

 

3 ) 2번에서 방문하지않은 미네랄은 공중에 떠있으므로 바닥까지 내려준다

 

4 ) 바닥에 내리면서 중간에 다른 클러스터 위로 떨어지거나, 바닥으로 떨어지면 멈추고 다시 1 ) 번으로 돌아간다.

 

 

* 떨어지면서 걸치는 경우도있다. 예를들어 ㄱ 모양의 바닥과 연결된 클러스터랑 T 같은 공중에 떠있는 클러스터가

 

대상이된다면 걸치게된다. 이경우를 계산하기위하여 boolean 변수 2개를 사용하여 떨어지는 모둔 좌표에 대해서

 

확인해준다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
	static char map[][] ; 
	static int r,c,ny,nx,nowx,nowy,arrow[];
	static int dy[] = {0,0,-1,1} ,dx[] = {-1,1,0,0};
	static ArrayDeque<int []> dq = new ArrayDeque<>();
	static boolean visit[][];
	
	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());
		map= new char[r][c];
		for(int y= 0 ; y < r ; y++) map[y] = br.readLine().toCharArray();
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		arrow = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int index= 0 ; index < n ; index++) {arrow[index] = r-(Integer.parseInt(st.nextToken()));}
		for(int index= 0 ; index < n ; index++) {
			int row = arrow[index]; int i;
			if(index % 2 == 0) {
				for( i = 0 ; i < c ; i ++) {
					if(map[row][i] =='x') {
						map[row][i] ='.';break;
						}
					}
				}
			else {
				for( i = c-1 ; i >=0 ; i --) {
					if(map[row][i] =='x') {
						map[row][i] ='.';break;
						}
					}
				}
			
			if((index%2==0 && i ==c) || (index%2==1 && i == -1)) continue;	// 맵에 변화가 없음
			
			visit = new boolean[r][c];
			
			spread();
			down();
		}	
		
		
		
		// 답 출력
		for(int y = 0 ; y < r ; y++) {
			for(int x= 0 ; x< c ; x++) {
				System.out.print(map[y][x]);
			}
			System.out.println();
		}
	}

	private static void spread() {
		// 미네랄이 한개 깨진 맵
		// 클러스터가 나뉘어져 공중에 떠있는것을 확인하기 위해서 바닥 R-1 행만 BFS를 돌려본다
		// 이와 연결되어있지 않다면, 공중에 떠있는것
		for(int x  = 0 ; x < c ; x++) {
			if(!visit[r-1][x] && map[r-1][x] =='x') {
				visit[r-1][x] = true;
				dq.add(new int[] { r-1,x});
				while(!dq.isEmpty()) {
					int now[] = dq.poll();
					nowx = now[1]; nowy = now[0];
					for(int j= 0 ; j< 4 ; j++) {
						ny = nowy + dy[j];
						nx = nowx + dx[j];
						if(ny >= 0 && nx >= 0 && ny < r && nx < c) {
							if(map[ny][nx]=='x' && !visit[ny][nx]) {
								visit[ny][nx] = true;
								dq.add(new int[] {ny,nx});
							}
						}
					}
				}
			}
		}
		
	}

	private static void down() {
		// 공중에 떠있는 미네랄은 MAP값이 X이고 방문처리가 되지않았을것
		// BOOL 변수 2개를 사용해 계속내릴것인지 그만내릴것인지 판별한다.
		// connect = 공중에 클러스터가 떠있는지를 표시하는변수
		// conti = 공중의 클러스터가 내려오면서 기존에 땅과 연결된 클러스터랑 만났는지 여부
		boolean connect = true , conti = false;
		while(connect) {
			connect = false;
			for(int y = r-1 ; y >= 0 ; y--) {
				for(int x= c-1 ; x >= 0 ; x--) {
					if(map[y][x] =='x' && !visit[y][x]) {
						connect = true;
						// 내릴 대상들
						map[y+1][x] = map[y][x]; map[y][x] ='.';
						if((y+1 == r-1) ||(map[y+2][x] == 'x' && visit[y+2][x])) {
							conti =true;
						}
					}
				}
			}
			if(conti) connect = false;
		}
	}
}

 

---