• 백준 11559번 Puyo Puyo :: 마이구미
    알고리즘 풀이/그래프 2017. 12. 11. 11:10
    반응형

    이 글은 백준 알고리즘 문제 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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    static int[] dx = { -101};
    static int[] dy = { 0-10};
    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 (<= nx && nx < && <= 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;
        }
    }
    cs


    반응형

    댓글 0

Designed by Tistory.