[백준] 11559. Puyo Puyo

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

11559번: Puyo Puyo

---

[ 문제 풀이 ]

1. 4개 이상 모여있는 뿌요들을 없애고, 아래로 떨어뜨린 map 을 그 전과 같은지 확인하기 위해서 copy_map 에 초기값을 복사해 놓고 연산이 끝난 후에 비교해서 같으면 더 이상 연산을 안하고 break 로 답을 출력합니다.

2. DFS(x좌표, y좌표, 뿌요의 종류) 를 통해서 뿌요의 종류가 4개이상 상하좌우로 연결되어 있으면 뿌요들을 모두 . 으로 바꿔줍니다.

3. 뿌요들이 없어지고 빈공간에 나머지 뿌요들을 떨어뜨려 줍니다.

4. 처음에 저장했던 copy_map 과 뿌요들을 없애고 떨어뜨린 map의 상태가 같으면 while 문을 빠져나오고 몇번 연쇄가 일어났는지 저장했던 answer을 출력하면 정답입니다.

---

import java.util.Scanner;
import java.util.ArrayList;


// 11559 Puyo Puyo

public class Main {

	static int N = 12, M = 6, len, answer = 0;
	static char[][] map = new char[N][M], copy_map = new char[N][M];
	static boolean[][] visited;
	static int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
	static ArrayList<Pair> list;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		for (int i = 0; i < N; i++) {
			String st = sc.nextLine();
			for (int j = 0; j < st.length(); j++) {
				map[i][j] = st.charAt(j);
			}
		}

		while (true) {

			// map을 copy_map에 복사

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					copy_map[i][j] = map[i][j];
				}
			}

			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (map[i][j] != '.') {
						len = 0;
						visited = new boolean[N][M];
						list = new ArrayList();

						// 뿌요들이 4개 이상 모였는지 확인
						DFS(i, j, map[i][j]);

						// 뿌요들이 4개 이상 모였으면 . 으로 바꾸기
						if (len >= 4)
							for (int k = 0; k < list.size(); k++)
								map[list.get(k).x][list.get(k).y] = '.';
					}
				}
			}

			// 뿌요 아래로 떨어뜨리기
			for (int i = 0; i < M; i++) {
				for (int j = N - 2; j >= 0; j--) {
					if (map[j][i] != '.' && map[j + 1][i] == '.') {
						int r = j;
						while (r + 1 < N && map[r + 1][i] == '.') {
							map[r + 1][i] = map[r][i];
							map[r][i] = '.';
							r++;
						}
					}
				}
			}

			boolean flag = false;

			// copy_map과 map이 똑같은지 검사 똑같으면 뿌요들의 연쇄가 끝난것이기 때문에 정답 출력하고 종료
			Outter: for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (copy_map[i][j] != map[i][j]) {
						flag = true;
						break Outter;
					}
				}
			}

			if (!flag)
				break;

			answer++;

		}

		System.out.println(answer);

	}

	public static void DFS(int x, int y, char data) {
		len++;
		list.add(new Pair(x, y));
		visited[x][y] = true;

		for (int i = 0; i < 4; i++) {
			int nx = x + dir[i][0];
			int ny = y + dir[i][1];

			if (isInside(nx, ny) && !visited[nx][ny] && map[nx][ny] == data) {
				DFS(nx, ny, data);
			}

		}

	}

	public static boolean isInside(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < M;
	}

}

class Pair {
	int x;
	int y;

	Pair(int x, int y) {
		this.x = x;
		this.y = y;
	}
}