문제
뿌요뿌요 게임은 6열 12행의 격자판 위에서 진행된다. 각 칸에는 R, G, B, P, Y 중 하나의 색깔 뿌요 또는 빈 칸(.)이 있다.
같은 색깔의 뿌요가 4개 이상 상하좌우로 연결되어 있으면 터진다. 한 번의 연쇄에서 가능한 모든 뿌요가 동시에 터지고, 터진 자리가 비워진 후 위의 뿌요들이 아래로 떨어진다. 이 과정을 더 이상 터질 뿌요가 없을 때까지 반복한다. 총 연쇄 횟수를 구하는 문제이다.
입력
12개의 줄에 6개의 문자가 주어진다. 각 문자는 ., R, G, B, P, Y 중 하나이다.
출력
총 연쇄 횟수를 출력한다.
예제
입력
......
......
......
......
......
......
......
......
.RRR..
RRRR..
BBBBB.
BBBB..출력
4풀이
핵심 아이디어: BFS로 동일 색 연결 컴포넌트를 탐색하고, 4개 이상이면 동시에 제거한다. 제거 후 중력(아래로 떨어짐)을 적용하고, 변화가 없을 때까지 반복한다.
- 반복 시작:
changed플래그를false로 초기화한다. - BFS 탐색: 전체 격자를 순회하며 빈 칸이 아닌 셀에서 BFS를 실행해 같은 색깔의 연결된 셀 목록을 수집한다.
- 터뜨리기: 연결된 셀 수가 4 이상이면 모두
.으로 변경하고changed = true로 설정한다. - 중력 적용: 각 열에 대해 아래부터 위로 순회하면서 빈 칸이 있으면 위의 뿌요를 아래로 당긴다.
- 종료 조건:
changed가false이면 더 이상 터질 뿌요가 없으므로 반복을 종료한다. - 연쇄 카운트: 변화가 발생할 때마다
ans를 증가시킨다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class Day346BOJ11559뿌요뿌요 {
static int N = 12, M = 6, ans = 0;
static int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
static char[][] map = new char[N][M];
static boolean changed;
static boolean[][] visited;
static List<int[]> list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = 0; i < N; i++) {
String tmp = br.readLine();
for (int j = 0; j < M; j++) {
map[i][j] = tmp.charAt(j);
}
}
while (true) {
changed = false;
visited = new boolean[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
char c = map[i][j];
if (c != '.') {
list = new ArrayList<>();
bfs(c, i, j);
if (list.size() >= 4) {
changed = true;
for (int[] a : list)
map[a[0]][a[1]] = '.';
}
}
}
}
if (!changed)
break;
change();
// print();
ans++;
}
System.out.println(ans);
br.close();
}
private static void print() {
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
}
private static void bfs(char c, int idx, int jdx) {
Queue<int[]> q = new LinkedList<>();
list.add(new int[] { idx, jdx });
q.add(new int[] { idx, jdx });
visited[idx][jdx] = true;
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int dir = 0; dir < 4; dir++) {
int nr = cur[0] + dr[dir];
int nc = cur[1] + dc[dir];
if (index(nr, nc))
continue;
if (visited[nr][nc])
continue;
if (map[nr][nc] != c)
continue;
list.add(new int[] { nr, nc });
q.add(new int[] { nr, nc });
visited[nr][nc] = true;
}
}
}
private static boolean index(int nr, int nc) {
return nr < 0 || nr >= N || nc < 0 || nc >= M;
}
private static void change() {
for (int j = 0; j < M; j++)
for (int i = N - 1; i > 0; i--)
if (map[i][j] == '.')
for (int k = i - 1; k >= 0; k--)
if (map[k][j] != '.') {
map[i][j] = map[k][j];
map[k][j] = '.';
break;
}
}
}복잡도
- 시간: O(K * (N * M)) — K는 연쇄 횟수, 매 연쇄마다 격자 전체를 BFS 탐색 (최대 연쇄 수는 격자 크기에 비례)
- 공간: O(N * M) — visited 배열 및 BFS 큐