[BOJ] 백준 11559 Puyo Puyo

[문제]

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

 

[소스 코드]

import java.io.*;
import java.util.*;
public class Main {
	static boolean[][] visit;
	static char[][] map;
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	static class Puyo{
		int r,c;
		Puyo(int r,int c){
			this.r = r;
			this.c = c;
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		map = new char[12][6];
		for(int i=0;i<12;i++) {
			String s = br.readLine();
			for(int j=0;j<6;j++) {
				map[i][j] = s.charAt(j);
			}
		}
		int result = 0;
		while(true) {
			boolean check = false;
			visit = new boolean[12][6];
			
			for(int i=0;i<12;i++) {
				for(int j=0;j<6;j++) {
					if(map[i][j]!='.' && !visit[i][j]) {
						List<Puyo> list = bfs(i,j,map[i][j]);
						if(list.size()>=4) {
							for(Puyo p : list) {
								map[p.r][p.c] = '.';
							}
							check = true;
						}
					}
				}
			}
			if(!check) break;
			result++;
			gravity();
		}
		System.out.println(result);
	}
	private static List<Puyo> bfs(int i,int j,char c){
		List<Puyo> list = new LinkedList<>();
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {i,j});
		visit[i][j] = true;
		list.add(new Puyo(i,j));
		
		while(!q.isEmpty()) {
			int[] curr = q.poll();
			for(int d=0;d<4;d++) {
				int nr = curr[0] + dr[d];
				int nc = curr[1] + dc[d];
				if(nr<0 || nr>=12 || nc<0 || nc>=6) continue;
				if(!visit[nr][nc] && map[nr][nc]==c) {
					q.offer(new int[] {nr,nc});
					list.add(new Puyo(nr,nc));
					visit[nr][nc] = true;
				}
			}
		}
		return list;
	}
	private static void gravity() {
		for(int j=0;j<6;j++) {
			int idx = 11;
			for(int i=11;i>=0;i--) {
				if(map[i][j]!='.') {
					map[idx--][j] = map[i][j];
				}
			}
			while(idx>=0) {
				map[idx--][j] = '.';
			}
		}
	}
}