문제

12*N에 빨, 초, 파, 보, 노랑의 뿌요들이 주어진다. 같은 색의 뿌요들이 상하좌우로 4개 이상 연결되어있으면 한꺼번에 없어진다. 없어지고 나면 1번의 연쇄가 추가되고, 1번의 연쇄에서는 여러 개의 뿌요 그룹이 터질 수 있다. 뿌요들이 주어졌을 떄, 연속으로 일어나는 연쇄의 수를 계산해 출력하면 되는 문제이다.

풀이

1. map[12][6]에 뿌요를 1~6의 값으로 넣어준다.
2. while을 돌면서 터질 수 있는 뿌요가 있는지 bfs(i, j)로 체크한다.

• 이 때, 이중 포문과 이차원 boolean 배열로 방문하지 않은 뿌요 그룹이 있는지 체크하면서 bfs를 수행한다.
• flag는 터질 수 있는 뿌요 그룹이 없는 경우를 체크하기 위해 존재한다.

3. bfs(int x, int y)는 파라미터로 들어온 좌표부터 같은 값을 가지는 뿌요들을 탐색해 q에 넣어준다.

• 여기서 뿌요 그룹을 저장하기 위해 route라는 큐에 방문한 뿌요들을 넣어준다.
• route의 길이가 4 이상인 경우는 pop(route)로 해당 뿌요들의 값을 0으로 만들어 준다.

4. 뿌요 그룹이 터진 경우 (flag == true)
down()로 0위에 존재하는 뿌요들을 아래로 내린다.

소스 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ_11559 {
    static int[][] map;
    static boolean[][] visited;
    static final int mx = 12;
    static final int my = 6;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int count = 0;

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

        map = new int[mx][my];
        visited = new boolean[mx][my];

        for (int i = 0; i < mx; i++) {
            String[] input = br.readLine().split("");
            for (int j = 0; j < my; j++) {
                char val = input[j].charAt(0);
                if (val == '.') {
                    map[i][j] = 0;
                } else if (val == 'R') {
                    map[i][j] = 1;
                } else if (val == 'G') {
                    map[i][j] = 2;
                } else if (val == 'B') {
                    map[i][j] = 3;
                } else if (val == 'Y') {
                    map[i][j] = 5;
                } else {
                    map[i][j] = 6;
                }
            }
        }

        while (true) {
            boolean flag = false;
            visited = new boolean[mx][my];

            for (int i = 0; i < mx; i++) {
                for (int j = 0; j < my; j++) {
                    if (!visited[i][j] && map[i][j] != 0) {
                        if (bfs(i, j)) {
                            flag = true;
                        }
                    }
                }
            }

            if (flag) {
                count++;
                down();
            } else {
                System.out.println(count);
                break;
            }

        }
    }

    static boolean bfs(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        Queue<Point> route = new LinkedList<>();

        q.add(new Point(x, y));
        route.add(new Point(x, y));

        visited[x][y] = true;

        while (!q.isEmpty()) {
            Point p = q.poll();

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

                if (nx < 0 || ny < 0 || nx >= mx || ny >= my || visited[nx][ny]) {
                    continue;
                }

                if (map[nx][ny] == map[x][y]) {
                    q.add(new Point(nx, ny));
                    route.add(new Point(nx, ny));

                    visited[nx][ny] = true;
                }
            }
        }

        if (route.size() >= 4) {
            pop(route);
            return true;
        } else {
            return false;
        }
    }

    static void pop(Queue<Point> route) {
        while (!route.isEmpty()) {
            Point temp = route.poll();
            map[temp.x][temp.y] = 0;
        }
    }

    static void down() {
        for (int i = 0; i < my; i++) {
            for (int j = mx - 1; j > 0; j--) {
                if (map[j][i] == 0) {
                    for (int k = j - 1; k >= 0; k--) {
                        if (map[k][i] != 0) {
                            map[j][i] = map[k][i];
                            map[k][i] = 0;
                            break;
                        }
                    }
                }
            }
        }
    }

    static void print() {
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    static class Point {
        int x;
        int y;

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

문제가 귀여워서 그런지 푸는데 재밌었다.
문제 제대로 안 읽고 뿌요 색 4개만 입력받아서 헤멤