백준 16768번 - Mooyo Mooyo (java)

💡 문제 링크

https://www.acmicpc.net/problem/16768

 

💡 아이디어

테트리스 게임과 거의 동일한 문제이다.

1) bfs를 사용해서 인접한 같은 숫자의 그룹을 체크한다.

2) 칸의 수가 K 이상이면 그 칸들의 값을 0으로 바꾼다.

3) 중력이 적용되어 사이사이의 빈칸을 위의 칸들이 떨어져서 메꾼다.

4) 칸의 변화가 있었다면 1~3번 과정을 반복한다.

5) 더이상 칸의 변화가 없다면 종료한다.

 

의외의 부분에서 어려웠던 문제였다.

은근히 중력 적용하는 부분이 바로 잘 떠오르지 않았고, 떠올려서 푼 풀이는 오류가 있었다.

이 부분은 스터디원의 코드가 좋아서 참고하여서 해결하였다.

 

💡 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_G4_16768_MooyoMooyo {
    static int N, K, map[][];
    static boolean visited[][];
    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};
    static boolean changed;

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][10];

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < 10; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        //------------------ 입력 완료

        do {
            changed = false;
            visited = new boolean[N][10];
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < 10; j++) {
                    if (map[i][j] != 0 && !visited[i][j]) {
                        bfs(i, j); //사라진 칸 확인
                    }
                }
            }
            gravity(); //중력 적용
        } while (changed); //사라진 칸이 있으면 반복

        //정답 출력
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 10; j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
    }

    private static void gravity() {
        for (int j = 0; j < 10; j++) {
            int emptyRow = N - 1;
            for (int i = N - 1; i >= 0; i--) {
                if (map[i][j] != 0) {
                    if (emptyRow != i) {
                        map[emptyRow][j] = map[i][j];
                        map[i][j] = 0;
                    }
                    emptyRow--;
                }
            }
        }
    }

    public static void bfs(int r, int c) {
        int count = 1;
        Queue<int[]> q = new ArrayDeque();
        List list = new ArrayList<int[]>();
        q.offer(new int[]{r, c});
        list.add(new int[]{r, c});
        visited[r][c] = true;

        while (!q.isEmpty()) {
            int cur[] = q.poll();
            int cr = cur[0];
            int cc = cur[1];
            for (int d = 0; d < 4; d++) {
                int nr = cr + dr[d];
                int nc = cc + dc[d];
                if (!check(nr, nc) || visited[nr][nc]) {
                    continue;
                }
                if (map[nr][nc] == map[cr][cc]) {
                    count++;
                    list.add(new int[]{nr, nc});
                    q.offer(new int[]{nr, nc});
                    visited[nr][nc] = true;
                }
            }
        }
        if (count >= K) {
            for (int i = 0; i < list.size(); i++) {
                int[] cell = (int[]) list.get(i);
                map[cell[0]][cell[1]] = 0;
            }
            changed = true;
        }
    }

    public static boolean check(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < 10;
    }
}