백준 11559번: Puyo Puyo

문제 설명

• https://www.acmicpc.net/problem/11559
• 현재 상황에서 몇 번의 연쇄가 발생하는지 계산하는 문제입니다.

접근법

• 뿌요가 터지는지 확인하기 위해서 BFS를 실행합니다.
  • 4개 이상 인접해야 터지기 때문에 곧바로 터뜨리지 않고 임시 배열에 값을 담아둡니다.
  • 임시 배열의 크기가 4이상일 때 뿌요를 터뜨립니다.
• 뿌요가 터진 후 공중에 떠 있는 블록을 내려야 합니다.
  • 열 방향, 아래에서 위로 탐색을 진행하면서 ((0,12)->(0,0), (1,12)->(1,0), ...)
  • 만약 맨아래 뿌요가 아닌 어떤 뿌요의 아래가 빈칸이라면
  • 해당 열을 다시 맨아래부터 순회하면서 처음 빈칸인 곳을 찾아
  • 공중에 떠 있는 뿌요와 swap합니다.

정답

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

public class Main {
	static int N = 12;
	static int M = 6;
	static int[] dx = {0,1,0,-1};
	static int[] dy = {1,0,-1,0};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[][] board = new char[N][M];
		for (int i = 0; i < N; i++) {
			board[i] = br.readLine().toCharArray();
		}
		int chain = 0;
		while(true) {
			boolean[][] v = new boolean[N][M];
			boolean flag = false;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if(board[i][j] != '.') {
						v[i][j] = true;
						flag = flag | BFS(v,board,new int[] {i,j});
					}
				}
			}
			if(flag) {
				chain++;
			}else {
				break;
			}			
			Gravity(board);

			
		}
		System.out.println(chain);
		
	}
	
	public static boolean BFS(boolean[][] v, char[][] board, int[] start) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(start);
		List<int[]> candi = new LinkedList<int[]>();
		candi.add(start);
		while(!q.isEmpty()) {
			int[] now = q.poll();
			for (int d = 0; d < 4; d++) {
				int nx = now[0] + dx[d];
				int ny = now[1] + dy[d];
				if(0 <= nx && nx < N && 0 <= ny && ny < M && !v[nx][ny] && board[nx][ny] == board[start[0]][start[1]]) {
					v[nx][ny] = true;
					q.add(new int[] {nx,ny});
					candi.add(new int[] {nx,ny});
				}
			}
		}
		if(candi.size()>=4) {
			for (int i = 0; i < candi.size(); i++) {
				int[] now = candi.get(i);
				board[now[0]][now[1]] = '.';
			}
			return true;
		}
		return false;
		
	}
	
	public static void Gravity(char[][] board) {
		for (int j = 0; j < M; j++) {
			for (int i = N-2; i >=0 ; i--) { // 맨 밑(N-1)에는 확인할 필요X
				if(board[i][j] != '.' && board[i+1][j] == '.') { // 자기 아래가 빈공간이면
					Here: for (int k = N-1; k > i; k--) { // 해당 열의 처음부터 i까지 거슬러 올라오면서 
						if(board[k][j] == '.') { // 처음 빈공간인 위치와 swap함
							board[k][j] = board[i][j];
							board[i][j] = '.';
							break Here;
						}
						
					}
				}
			}
		}
	}

}