백준 11559번 Puyo Puyo :: 마이구미

이 글은 백준 알고리즘 문제 11559번 "Puyo Puyo" 를 풀이한다.

시뮬레이션 문제로써, 시나리오를 정확히 이해한 후 그대로 구현하면 된다.

본인은 그 과정속에 DFS를 통해 해결했다.

문제 링크 - https://www.acmicpc.net/problem/11559

뿌요뿌요의 룰은 다음과 같다.

필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.

뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다.

뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.

아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.

터질 수 잇는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.

남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!

문제는 애니팡 같은 게임을 생각하면 쉽게 이해할 수 있다.

주의할 점은 터질 수 있는 뿌요가 여러 그룹에 있을 수 있다는 것이다.

....BB
....BB
RRRRGG
GGRRRR

위와 같이 1번의 연쇄에서 터지는 그룹이다.

그룹이 1번의 연쇄에서 각 그룹이 다른 색을 가지더라도 무조건 4개이상으로 구성된 그룹은 터진다는 것을 말하고 싶은 것이다.

시뮬레이션 결과는 다음과 같다.

1. 모든 곳을 탐색하면서 터트릴 수 있는 4개이상의 뿌요인 그룹 찾기 (그룹은 0개 이상이다.)
2. 찾은 뿌요 그룹 모두 터트리기
3. 중력으로 인해 터트린 곳을 메꾸기 위해 맵 다시 그리기

본인은 뿌요를 찾기 위한 메소드, 다시 그리기 위한 메소드 크게 2개를 통해 구현했다.

dfs()

public static void dfs(int y, int x, char ch) {
    for (int i = 0; i < 4; i++) {
        int nx = dx[i] + x;
        int ny = dy[i] + y;

        if (0 <= nx && nx < 6 && 0 <= ny && ny < 12) {
            if (!visited[ny][nx] && map[ny][nx] == ch) {
                list.add(new Point(ny, nx));
                visited[ny][nx] = true;
                dfs(ny, nx, ch);
            }
        }
    }
}

전형적인 DFS 방식이고, 뿌요 좌표를 기억하기 위해 ArrayList 를 사용했다.

좌표를 기억하는 이유는 4개이상일 때만 터트리기 때문에 기억했다가 조건이 성립되면 그때 터트리기 위함이다.

paint() 

public static void paint() {
    for (int i = 0; i < 6; i++) {
        for (int j = 10; j >= 0; j--) {
            for (int k = 11; k > j; k--) {
                if (map[j][i] != '.' && map[k][i] == '.') {
                    map[k][i] = map[j][i];
                    map[j][i] = '.';
                    break;
                }
            }
        }
    }
}

중력에 의해 가장 아래로 떨어지게 됨으로써, 삼중 반복문을 통해 구현된다.

가장 아래부터 아래를 기준으로 채워나갈 수 있다.

관련 풀이 문제 - DFS 문제 카테고리

Github - https://github.com/hotehrud/acmicpc/tree/master/Simulation

static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static char[][] map = new char[12][6];
static boolean[][] visited;
static ArrayList<Point> list;
 
private void solve() {
    int ans = 0;
 
    for (int i = 0; i < 12; i++) {
        map[i] = sc.readLine().toCharArray();
    }
 
    // 1. 모든 곳을 돌면서 터트릴 수 있는 뿌요 찾기(크기 4이상).
    // 2. 터트릴 수 있는 뿌요 있다면 모두 터트리기.
    // 3. 터트린 곳 메꾸기 위해 맵 다시 그리기
 
    while (true) {
        boolean flag = false;
        visited = new boolean[12][6];
 
        // 터트릴 수 있는 뿌요가 여러 그룹으로 나누어 있을 수 있기 때문에 하나의 정점을 기준으로 모두 탐색.
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 6; j++) {
                if (!visited[i][j] && map[i][j] != '.') {
                    list = new ArrayList<Point>();
                    dfs(i, j, map[i][j]);
                    if (list.size() >= 4) {
                        flag = true;
                        for (Point p : list) {
                            map[p.y][p.x] = '.';
                        }
                    }
                }
            }
        }
 
        if (!flag) {
            break;
        } else {
            ans++;
        }
 
        paint();
    }
    System.out.println(ans);
}
 
public static void paint() {
    for (int i = 0; i < 6; i++) {
        for (int j = 10; j >= 0; j--) {
            for (int k = 11; k > j; k--) {
                if (map[j][i] != '.' && map[k][i] == '.') {
                    map[k][i] = map[j][i];
                    map[j][i] = '.';
                    break;
                }
            }
        }
    }
}
 
public static void dfs(int y, int x, char ch) {
    for (int i = 0; i < 4; i++) {
        int nx = dx[i] + x;
        int ny = dy[i] + y;
 
        if (0 <= nx && nx < 6 && 0 <= ny && ny < 12) {
            if (!visited[ny][nx] && map[ny][nx] == ch) {
                list.add(new Point(ny, nx));
                visited[ny][nx] = true;
                dfs(ny, nx, ch);
            }
        }
    }
}
 
public static class Point {
    int y, x;
 
    Point(int y, int x) {
        this.y = y;
        this.x = x;
    }
}