[백준] 11559 Puyo Puyo

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

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

public class B11559 {
	static char arr[][] = new char[12][6];
	static int[][] delta = {{1,0},{0,1},{-1,0},{0,-1}};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		for (int i = 0; i < 12; i++) { 
			String temp = br.readLine(); 
			for (int j = 0; j < 6; j++) { 
				arr[i][j] = temp.charAt(j); 
			} 
		}
		
		int count = 0;
		boolean flag = true;
		
		while (flag) {
			flag = false; 
			for (int i = 0; i < 12; i++) { 
				for (int j = 0; j < 6; j++) { 
					if (arr[i][j] != '.') { 
						ArrayList<int[]> list = find(i, j); 
						if (list.size() >= 4) { 
							for (int k = 0; k < list.size(); k++) {
								int[] ind = list.get(k); 
								arr[ind[0]][ind[1]] = '.'; 
							} 
							flag = true; 
						}
					}
				}
			}
			// 블록이 없어진 경우
			if (flag) { 
				count++; 
				down(); 
			} 
		}	
		System.out.println(count);
	}
	
	private static ArrayList<int[]> find(int x, int y) {
		// bfs로 찾은 블록을 list에 넣기
		ArrayList<int[]> list = new ArrayList<>(); 
		Queue<int[]> q = new LinkedList<>(); 
		q.add(new int[] {x,y}); 
		char temp = arr[x][y]; 
		boolean[][] check = new boolean[12][6]; 
		check[x][y] = true; 
		while (!q.isEmpty()) { 
			int[] node = q.poll(); 
			list.add(node);
			for (int i = 0; i < 4; i++) {
				int nx = node[0] + delta[i][0];
				int ny = node[1] + delta[i][1]; 
				if (notin(nx, ny)) continue;
				if (arr[nx][ny] == temp && !check[nx][ny]) { 
					q.add(new int[] {nx, ny}); 
					check[nx][ny] = true;
				} 
			} 
		}
		return list; 
	}
		
	private static void down() {
		// stack을 이용해 줄마다 처리
		Stack<Character> stack = new Stack<>(); 
		for (int j = 0; j < 6; j++) { 
			for (int i = 0; i < 12; i++) { 
				if (arr[i][j] != '.') 
					stack.push(arr[i][j]); 
				} 
			// 아래쪽부터 채우기
			for (int i = 11; i >= 0; i--) { 
				if (stack.isEmpty()) arr[i][j] = '.'; 
				else arr[i][j] = stack.pop(); 
			} 
		}

	}

	private static boolean notin(int x, int y) { 
		 return x < 0 || x >= 12 || y < 0 || y >= 6; 
	}

}