문제

풀이 과정

요약

시뮬레이션 문제. 이거 삼성 기출 같은데? (아니었다고 한다.)

상세

1. 문제에서 중요한 부분은 다음과 같다.

   • 뿌요가 현 시점에서 4개이상 모였을 때 폭발이 일어난다.

   • 해당 문제는 폭발이 연쇄적으로 일어난 연쇄 갯수를 물어본다. 즉, 폭발 갯수하고는 상관없다. 예를들어, 어느 시점에서 4개이상 모인 뿌요가 3개 있고, 3개가 터진다고 하여도, 연쇄 과정은 총 1번이므로, 1번만 카운트되는 경우가 있다.

   • 폭발이 완료된 후, 빈공간이 생기고, 빈공간 위에 뿌요들이 존재한다면 뿌요를 중력에 의해 내려오도록 해야한다.

2. 먼저 모든 뿌요를 시작으로 완전탐색을 할 것이다. 현재 뿌요와 동일한 뿌요이면서 인접한 경우에만 이동한다. BFS 로 탐색을 하는데, 현재의 뿌요가 어느정도 연결되어 있는지를 확인하고자, tList 를 생성해주었다.

3. 해당 tList 에 모인 좌표가 4 이상인 경우, 뿌요가 폭발할 수 있다. 단 탐색이 끝나자마자 바로 폭발시키기 보다는 다른 뿌요가 4개이상 모이는 경우도 있기에 이를 모두 확인한 후 한꺼번에 폭발시켜야 한다. list 를 생성하여, 매 BFS 를 통해 tList 의 4 이상 모인 뿌요들을 list 로 이관하였다. 이렇게 하면 현 시점에서 폭발할 수 있는 모든 뿌요의 좌표를 한데 모으는 것이 가능하다. 반대로 만약 list 에 아무것도 없는 경우가 더이상 뿌요가 폭발할 수 있는 경우의 수가 없는 것이므로, 최종적으로 게임이 종료되는 것을 의미하게 된다.

4. 모든 뿌요의 BFS 탐색이 끝나고, 만약 list 에 폭발할 수 있는 경우의 수가 존재한다면 이때가 연쇄 수를 늘려야하는 상황이다. ans 를 1 더해주고, list 좌표의 뿌요들을 빈공간으로 만들어주자.

5. 이제 뿌요를 재배치해야한다. 행을 기준으로 탐색할 것이다. 행마다 가장 아래부터 빈공간이 있는지 살펴본다. 만약 빈공간을 찾았을때 해당 빈공간을 시작으로 남은 열을 탐색했을 때 뿌요가 존재하는 경우, 빈공간에서 해당 뿌요까지 만큼의 차이를 기존 뿌요 좌표에 더한 값이 뿌요가 이동해야하는 좌표값이다. $[r+diff][c]$

6. 재배치까지 모두 끝났다면 이번 연쇄에서 해야할 것은 모두 끝났다. 다시 폭발할 수 있는 경우를 찾아야 하므로, 방문처리와 list 를 초기화해주자.

정답

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 Main {
    static char[][] map;
    static boolean[][] visited;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, -1, 0, 1};
    static List<int[]> list;
    static int ans;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        map = new char[12][6];
        for (int i = 0; i < 12; i++) {
            map[i] = br.readLine().toCharArray();
        }

        while(true) {
            visited = new boolean[12][6];
				    list = new ArrayList<>();
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 6; j++) {
                    if (map[i][j] != '.' && !visited[i][j]) {
                        visited[i][j] = true;
                        BFS(i, j);
                    }
                }
            }
            if(list.size() <= 0) {
                break;
            } else {
                ans++;
                for(int[] pos : list) map[pos[0]][pos[1]] = '.';
                outer :for(int c=0; c<6; c++) {
                    for(int r=11; r>=0; r--) {
                        if (map[r][c] == '.') {
                            int step = 1;
                            for (int k = r-1; k >= 0; k--) {
                                if (map[k][c] == '.') step++;
                                else {
                                    map[k + step][c] = map[k][c];
                                    map[k][c] = '.';
                                }
                            }
                            continue outer;
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }

    private static void BFS(int i, int j) {
        Queue<int[]> q = new LinkedList<>();
        List<int[]> tList = new ArrayList<>();
        q.add(new int[]{i, j});
        tList.add(new int[]{i, j});

        while (!q.isEmpty()) {
            int[] curr = q.poll();
            for (int d = 0; d < 4; d++) {
                int nr = curr[0] +dr[d];
                int nc = curr[1] +dc[d];
                if(nr<0 || nc<0 || nr>=12 || nc>=6 || visited[nr][nc] || map[i][j] != map[nr][nc]) continue;

                visited[nr][nc] = true;
                q.add(new int[] {nr,nc});
                tList.add(new int[] {nr,nc});
            }
        }

        if(tList.size() >= 4) {
            for(int[] pos : tList) {
                list.add(pos);
            }
        }
    }
}