[백준] 11559. Puyo Puyo (Java)

 

11559번: Puyo Puyo

 

풀이

• 완전 시뮬레이션 문제 = method를 많이 만들어야 함
• 처음에 뿌요 위치를 큐에 가져온다. (getPuyo()로 구현)
• 이제 뿌요 있는곳만 터트릴 수 있는지 확인
• 터트릴 수 있는 얘들 싹 모아서 비우고 맵 정리
• 한 연쇄가 끝나면 정답 카운트++

 

풀기 전 의문점

위에서부터 터짐? 아래서부터 터짐?
동시에 두 개 이상 터지면 어떻게 됨?

• 동시에 터져야 한다.
• 여러번 터져도 연쇄는 한 번만 친다.

 

터지는 뿌요를 찾았다. 이제 이걸 어떻게 맵에서 없애지?

1. 터트릴 후보를 큐에 넣는다. (BFS(x, y)에서 네 개 이상 덩어리면 willBePopped 큐에 넣기)
2. map[x][y] = '.'로 바꾼다. (popPuyo()로 구현)
3. column을 돌면서 밑으로 내린다. (arrangeMap()로 구현)

• arrangeMap()에선 우선 .이 제일 처음으로 나온 위치를 baseline으로 설정하고 그 뒤로 뿌요가 나올때 마다 바로바로 .인 자리로 바꿔치기 해줬다.

---

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static char[][] map = new char[14][8];
    static int ans;
    static int[] px = new int[]{1, 0, -1, 0};
    static int[] py = new int[]{0, 1, 0, -1};
    static boolean[][] visited;
    static Queue<Coord> puyos, willBePopped;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for (int i = 1; i <= 12; i++){
            char[] arr = br.readLine().toCharArray();

            for (int j = 1; j <= 6; j++)
                map[i][j] = arr[j - 1];
        }

        while (true) {
            if (!puyoPuyo()) break;
            ans++;
        }

        bw.write(String.valueOf(ans));
        br.close();
        bw.close();
    }

    public static boolean puyoPuyo() {
        puyos = new LinkedList<>();
        willBePopped = new LinkedList<>();
        visited = new boolean[14][8];

        getPuyo();

        int size = puyos.size();
        for (int i = 0; i < size; i++) {
            int x = puyos.peek().x;
            int y = puyos.peek().y;
            puyos.poll();
            if (visited[x][y]) continue;
            visited[x][y] = true;
            BFS(x, y);
        }

        if (willBePopped.isEmpty()) return false;
        else {
            visited = new boolean[14][8];
            while(!willBePopped.isEmpty()) {
                int x = willBePopped.peek().x;
                int y = willBePopped.peek().y;
                willBePopped.poll();

                visited[x][y] = true;
                popPuyo(x, y);
            }
            arrangeMap();
        }
        return true;
    }

    public static void arrangeMap() {
        for (int j = 1; j <= 6; j++) {
            for (int i = 12; i >= 1; i--) {
                if (map[i][j] == '.') {
                    int baseLine = i;
                    for (int h = baseLine - 1; h >= 1; h--) {
                        if (map[h][j] != '.') {
                            map[i--][j] = map[h][j];
                            map[h][j] = '.';
                        }
                    }
                }
            }
        }
    }

    public static void popPuyo(int x, int y) {
        char color = map[x][y];
        map[x][y] = '.';
        Queue<Coord> q = new LinkedList<>();
        q.offer(new Coord(x, y));

        while(!q.isEmpty()) {
            int a = q.peek().x;
            int b = q.peek().y;
            q.poll();

            for (int d = 0; d < 4; d++) {
                int nx = a + px[d];
                int ny = b + py[d];
                if (map[nx][ny] != color || visited[nx][ny]) continue;

                visited[nx][ny] = true;
                map[nx][ny] = '.';
                q.offer(new Coord(nx, ny));
            }
        }
    }

    public static void BFS(int x, int y) {
        int cnt = 1;
        char color = map[x][y];
        Queue<Coord> q = new LinkedList<>();
        q.offer(new Coord(x, y));

        while(!q.isEmpty()) {
            int a = q.peek().x;
            int b = q.peek().y;
            q.poll();

            for (int d = 0; d < 4; d++) {
                int nx = a + px[d];
                int ny = b + py[d];

                if (map[nx][ny] != color || visited[nx][ny]) continue;
                cnt++;
                visited[nx][ny] = true;
                q.offer(new Coord(nx, ny));
            }
        }

        if (cnt >= 4) willBePopped.offer(new Coord(x, y));
    }

    public static void getPuyo() {
        for (int i = 1; i <= 12; i++)
            for (int j = 1; j <= 6; j++)
                if (map[i][j] != '.') puyos.offer(new Coord(i, j));
    }

    static class Coord {
        int x;
        int y;

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

}