[백준] 11559 Puyo Puyo

문제 출처: www.acmicpc.net/problem/11559

11559번: Puyo Puyo

: 필드에 여러 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 바닥이나 다른 뿌요를 만날때까지 아래로 떨어진다.

: 같은 색의 뿌요가 4개 이상이 되면 한꺼번에 없어진다.

: 주의해야 할 점은 전체 필드의 뿌요는 한번에 터지고, 중력의 영향을 받아 밑으로 떨어지고, 다시 한판에서 터지고를 반복한다는 것이다.

: 특히 중력의 영향을 받아 떨어지는 메소드 구현시 0행의 뿌요들이 밑으로 떨어지지 않는지 확인해보는 것이 중요하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static char[][] map = new char[12][6];
	static class Point{
		int r, c, cnt;
		
		public Point(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}

		public Point(int r, int c, int cnt) {
			super();
			this.r = r;
			this.c = c;
			this.cnt = cnt;
		}
		
	}
	static int res = 0;
	public static void main(String[] args) throws IOException {
		for(int i = 0; i < 12; i++) {
			String tmp = br.readLine();
			for(int j = 0; j < 6; j++) {
				map[i][j] = tmp.charAt(j);
			}
		}
		search();
		System.out.println(res);
	}
	
	static int[] dr = {-1, 1, 0, 0};
	static int[] dc = {0, 0, -1, 1};
	private static void search() {
		boolean flag = false;
		for(int i = 11; i >= 0; i--) {
			for(int j = 0; j < 6; j++) {
				if(map[i][j] != '.' ) {
					if(bfs(i, j, map[i][j])) flag = true;
				}
			}
		}
		//한줄씩 밑에 빈칸 있으면 내리기
		down();
		if(flag) {
			res++;
			search();
		}
	}
	private static boolean bfs(int r, int c, char color) {
		int cnt = 0;
		boolean[][] v = new boolean[12][6];
		Queue<Point> q = new LinkedList<>();
		ArrayList<Point> arr = new ArrayList<>();
		q.offer(new Point(r, c));
		v[r][c] = true;
		arr.add(new Point(r, c));
		while(!q.isEmpty()) {
			Point cur = q.poll();
			cnt++;
			for(int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				if(nr < 0 || nr >= 12 || nc < 0 || nc >= 6 || map[nr][nc] != color || v[nr][nc]) continue;
				v[nr][nc] = true;
				q.offer(new Point(nr, nc));
				arr.add(new Point(nr, nc));
			}
			
		}
		if(cnt > 3) {
			for(int i = 0, size = arr.size(); i < size; i++) {
				Point cur = arr.get(i);
				map[cur.r][cur.c] = '.';
			}
			return true;
		}
		return false;
	}
	private static void down() {

		for(int i = 0; i < 11; i++) {
			for(int j = 0; j < 6; j++) {
				int temp = i;
				if(map[i][j] != '.' && map[i+1][j] == '.') {
					while(temp >= 0) {
						map[temp+1][j] = map[temp][j];
						map[temp][j] = '.';
						temp--;
					}

				}
			}
		}

	}
}