[백준] 11559번 : Puyo Puyo

문제

11559번: Puyo Puyo

 

접근 방식

구현해야 할 기능은 크게 세 가지로

첫 번째는 같은 뿌요가 4개 이상 이어진 지 확인하고 터트리는 것이고,

두 번째는 남은 뿌요들을 빈 공간으로 내려주는 기능이고,

마지막은 4개 이상이 이어져 터진 경우 위 과정을 재귀호출을 통해 반복하는 것이다.

 

우선 첫 번째 기능은 필드를 순회하며

뿌요를 발견할시 BFS로 같은 뿌요인 경우만 탐색을 하며

기록해 두었다 4개 이상인 경우에는

기록해 둔 좌표의 뿌요들을 빈 공간으로 바꿔준다.

 

다음으로 두 번째 기능은 필드를 열을 기준으로 행을 거꾸로 순회하며

뿌요 발견 시 가장 밑 인덱스부터 채워주면 된다.

 

마지막 기능은 첫 번째 기능에서 터진 경우 폭발 여부를 기록해 두었다가

폭발을 했다면 재귀호출을 진행하고 그렇지 않다면 넘어가면 된다.

 

풀이

class Main {
    
	static int max = 0;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static char[][] fields = new char[12][6];
	static boolean[][] isVisited = new boolean[12][6];
	static Queue<Pair> q = new ArrayDeque<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for (int i = 0; i < 12; i++) {
			fields[i] = br.readLine().toCharArray();
		}

		solve();

		System.out.println(max);
	}

	static void solve() {
		boolean boom = false;

		for (int i = 0; i < 12; i++) {
			for (int j = 0; j < 6; j++) {
				if (isVisited[i][j]) continue;
				if (fields[i][j] != '.') {
					boolean b = bfs(i, j, fields[i][j]);
					if (b) boom = true;
				}
			}
		}

		if (boom) {
			max++;
			down();
			solve();
		}
	}

	static void down() {
		for (int start = 0; start < 6; start++) {
			int idx = 11;

			for (int i = 11; i >= 0; i--) {
				isVisited[i][start] = false;
				if (fields[i][start] != '.') {
					char tmp = fields[i][start];
					fields[i][start] = '.';
					fields[idx--][start] = tmp;
				}
			}
		}
	}

	static boolean bfs(int x, int y, char c) {
		Pair curP = new Pair(x, y);
		q.offer(curP);
		isVisited[x][y] = true;

		ArrayList<Pair> list = new ArrayList<>();
		list.add(curP);

		while (!q.isEmpty()) {
			Pair cur = q.poll();

			for (int dir = 0; dir < 4; dir++) {
				int nx = cur.x + dx[dir];
				int ny = cur.y + dy[dir];

				if (nx < 0 || nx >= 12 || ny < 0 || ny >= 6) continue;
				if (fields[nx][ny] != c || isVisited[nx][ny]) continue;

				isVisited[nx][ny] = true;
				Pair next = new Pair(nx, ny);
				list.add(next);
				q.offer(next);
			}
		}

		if(list.size() > 3) {
			for (Pair p : list) fields[p.x][p.y] = '.';
			return true;
		}

		return false;
	}

	static class Pair {
		int x, y;

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