Puyo Puyo [백준 11559][골드5][Java]

 

[광고 누르면 오늘의 행운 상승!!]

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

11559번: Puyo Puyo

밑으로 떨어지기 , 폭발하기를 구별하여서 구현하였다.

4개 이상 붙어있어야 폭발하기 때문에 q에 4개 이상 있을 때만 폭발시켰다.

import java.io.*;
import java.util.*;

public class Main {
	public static final int[] dx = {-1,0,1,0};
	public static final int[] dy = {0,1,0,-1};
	
	public static boolean visit[][];
	public static final int R = 12,C = 6;
	public static char[][] map;
	public static Queue<int[]> q;
	public static Queue<int[]> nq;
	public static int boom=0;
	public static boolean flag;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		map = new char[R][C];
		
		q = new LinkedList<>();
		nq = new LinkedList<>();
		
		for (int i = 0; i < R; i++) {
			char[] ch = br.readLine().toCharArray();
			for (int j = 0; j < C; j++) {
				map[i][j] = ch[j];
			}
		}
		while(!flag) {
			Drop();
			flag = Explode();
		}
		
		System.out.println(boom);
	}
	private static boolean Explode() {
		visit = new boolean[R][C];
		boolean flag = true;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(map[i][j] != '.' && !visit[i][j]) {
					visit[i][j] = true;
					q.add(new int[] {i,j});
					nq.add(new int[] {i,j});
					
					int n = bfs(map[i][j]);
					
					if(n>3) {
						while(!nq.isEmpty()) {
							int[] bbu = nq.poll();
							map[bbu[0]][bbu[1]] = '.';
						}
						
						flag = false;
					}else {
						nq.clear();
					}
					
				}
			}
		}
		if(!flag) boom++;
		return flag;
	}
	private static int bfs(char Color) {
		
		while(!q.isEmpty()) {
			int[] bbuyo = q.poll();
			
			for (int i = 0; i < 4; i++) {
				int nx = bbuyo[0] + dx[i];
				int ny = bbuyo[1] + dy[i];
				
				
				if(check(nx, ny) && map[nx][ny] == Color) {
					if(!visit[nx][ny]) {
						visit[nx][ny] = true;
						nq.add(new int[] {nx,ny});
						q.add(new int[] {nx,ny});
					}
				}
			}
			
		}
		return nq.size();
	}
	
	
	private static boolean check(int nx, int ny) {
		return nx >= 0 && nx < R && ny >= 0 && ny < C;
	}
	private static void Drop() {
		while(true) {
			//아래부터 검사
			int cnt = 0;
			for (int i = R-1; i >= 0; i--) {
				for (int j = 0; j < C; j++) {
					
					if(map[i][j] == '.') continue;
					
					int nx = i + dx[2];
					
					if(nx < R && map[nx][j] == '.') {
						map[nx][j] = map[i][j];
						map[i][j] = '.';
						cnt++;
					}
				}
			}
			if(cnt == 0) break;
		}
	}
}