/ BOJ

BOJ_11559_뿌요뿌요_JAVA

문제 : 뿌요뿌요

링크 : BOJ_11559_뿌요뿌요

접근 방식

BFS와 시뮬레이션이 적당히 섞여있는 문제라고 할 수 있다.

배열이 주어지면 해당 배열에서 몇 번의 체인이 터지는 지 알아내야하는 문제이다.

뿌요가 터지는 조건은 같은 색 뿌요가 4개 이상 연결되어 있는 경우이다.

뿌요가 터지고 난 후 위에 있는 뿌요들은 중력의 영향을 받아 아래로 떨어진다.

여러 개의 뿌요가 동시에 터질 수 있으면 동시에 터져야 한다. 한 타임에 여러 개 뿌요가 터져도 1체인으로 간주한다.

풀이 방식은 다음과 같다.

  1. 주어진 배열을 반복하며 4개 이상 같은 색이 모였는지 BFS로 탐색한다.

  2. 4개 이상인 경우, 뿌요를 터뜨려준다.

  3. 모든 배열의 탐색이 끝났다면, 공중에 떠 있는 뿌요를 아래로 내려준다.

  4. 한 번이라도 뿌요가 터졌다면 카운트를 증가시키고 1-3을 반복한다.

  5. 더 이상 뿌요가 터지지 않을 때 카운트를 출력하고 종료한다.

소스 코드

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

public class BOJ_11559_PuyoPuyo {

	static class Node {
		int x;
		int y;

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

	}

	static int dir[][] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

	static boolean check;

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		char[][] arr = new char[12][6];
		for (int i = 0; i < 12; i++) {
			arr[i] = in.readLine().toCharArray();
		}
		int chain = 0;
		while (true) {
			check = false;
			for (int i = 0; i < 12; i++) {
				for (int j = 0; j < 6; j++) {

					if (arr[i][j] != '.') {
						bfs(arr[i][j], new Node(i, j), arr);
					}

				}
			}

			if(!check) {
				System.out.println(chain);
				return;
			}else {
				chain++;
				for(int i=11;i>=0;i--) {
					for(int j=0;j<6;j++) {
						if(arr[i][j] == '.') {
							for(int k=i;k>=0;k--) {
								if(arr[k][j] != '.') {
									arr[i][j] = arr[k][j];
									arr[k][j] = '.';
									break;
								}
							}
						}
					}
				}
			}

//			for(int i=0;i<12;i++) {
//				System.out.println(Arrays.toString(arr[i]));
//			}
		}

	}

	static void bfs(char simbol, Node node, char[][] arr) {

		Queue<Node> queue = new LinkedList<>();
		boolean[][] visited = new boolean[12][6];

		queue.offer(node);
		visited[node.x][node.y] = true;
		int cnt = 1;
		while (!queue.isEmpty()) {

			Node temp = queue.poll();

			for (int d = 0; d < 4; d++) {
				int dx = temp.x + dir[d][0];
				int dy = temp.y + dir[d][1];

				if (dx < 0 || dx >= 12 || dy < 0 || dy >= 6) {
					continue;
				}

				if (arr[dx][dy] == simbol && !visited[dx][dy]) {
					visited[dx][dy] = true;
					queue.offer(new Node(dx, dy));
					cnt++;
				}

			}

		}
		if (cnt >= 4) {
			check = true;
			for (int i = 0; i < 12; i++) {
				for(int j=0;j<6;j++) {
					if(visited[i][j]) {
						arr[i][j] = '.';
					}
				}
			}
		}

	}

}

위에 적힌 함정들만 조심하면 되는데, 브론즈에 속해있다보니 쉽게 생각해서 많이 틀리는 것 같다. 나도 정답을 얻어내는데 4회의 실패가 있었고, 이는 문제의 정답 비율 27%와 가깝다.