[백준 / 골드4] 11559 Puyo Puyo (Java)

문제 보기

사용한 것

• 네 방향으로 방문하기 위한 dx, dy
• 방문 여부를 확인하기 위한 visited
• BFS로 뿌요들을 없앨 수 있는지 확인하기 위한 Queue
• 뿌요들을 없앨 수 있으면 기록하여 없애기 위한 Stack

풀이 방법

count 0부터 시작 -> 한 번에 없앨 수 있는 뿌요들 모두 없애기 -> 한 번이라도 없앴다면 1 증가 / 못 없앴다면 중단, 반환-> 뿌요들을 재정비하기 위해 바닥으로 떨어뜨리기 -> 반복...

• getCount()는 연쇄적으로 뿌요들을 없앨 수 있는 횟수를 구하는 메소드
  • 이중 for문을 통해 '.'가 아니고 방문하지 않았다면 explode() 시작
  • 여러 번의 explode()를 호출했으나 한 번도 없앨 수 없었다면 중단 후 count 반환
  • 없앴다면 down()을 호출하여 뿌요들을 재정비 후 다시 while문 돌면서 count 1 증가
• explode()는 상하좌우로 붙어있는 동일한 뿌요들을 없애기 위한 메소드
  • BFS를 통하여 같은 뿌요들을 탐색할때마다 count 1 증가
  • count가 4보다 크거나 같으면 없애고 true 반환
  • 작으면 없앨 수 없으므로 false 반환
• down()은 한 번에 없애는 것이 모두 끝나면 뿌요들을 바닥으로 떨어뜨리기 위한 메소드
• isOOB()는 범위 밖으로 벗어났는지 구하는 메소드

코드

public class Main {

    private static final int R = 12;
    private static final int C = 6;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[][] field = new char[R][C];
        for (int i = 0; i < R; i++) {
            field[i] = br.readLine().toCharArray();
        }
        System.out.println(getCount(field));
    }

    public static int getCount(char[][] field) {
        int count = 0;
        while (true) {
            boolean[][] visited = new boolean[R][C];
            boolean check = false;
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if (field[i][j] != '.' && !visited[i][j]) {
                        check |= explode(field, visited, i, j);
                    }
                }
            }
            if (!check) {
                break;
            }
            count++;
            down(field);
        }
        return count;
    }

    public static boolean explode(char[][] field, boolean[][] visited, int x, int y) {
        char c = field[x][y];
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{x, y});
        visited[x][y] = true;
        Stack<int[]> stack = new Stack<>();
        int count = 0;
        while (!q.isEmpty()) {
            int[] p = q.poll();
            count++;
            stack.push(p);
            for (int i = 0; i < 4; i++) {
                int nx = p[0] + dx[i];
                int ny = p[1] + dy[i];
                if (!isOOB(nx, ny) && !visited[nx][ny] && field[nx][ny] == c) {
                    q.offer(new int[]{nx, ny});
                    visited[nx][ny] = true;
                }
            }
        }
        boolean check = false;
        if (count >= 4) {
            while (!stack.isEmpty()) {
                int[] p = stack.pop();
                field[p[0]][p[1]] = '.';
            }
            check = true;
        }
        return check;
    }

    public static void down(char[][] field) {
        for (int i = 0; i < C; i++) {
            for (int j = R - 2; j >= 0; j--) {
                if (field[j][i] != '.') {
                    int y = j;
                    while (y + 1 < R && field[y + 1][i] == '.') {
                        y++;
                    }
                    if (y != j) {
                        field[y][i] = field[j][i];
                        field[j][i] = '.';
                    }
                }
            }
        }
    }

    public static boolean isOOB(int x, int y) {
        boolean check = false;
        if (x < 0 || x >= R || y < 0 || y >= C) {
            check = true;
        }
        return check;
    }
}