[백준(Baekjoon)] 11559. Puyo Puyo (java, BFS)

안녕하세요. 오늘은 백준의 11559번 Puyo Puyo 문제를 풀어보도록 하겠습니다. 프로그래머스 2021 하반기 백엔드 Dev-Matching시험을 보고 부족한 점을 많이 느꼈습니다. 이 문제가 Dev-Matching에서 나온 3번 문제랑 비슷해서 한번 풀어보고자 합니다.!

문제 링크

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

전체 코드

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

public class Main {

    static char[][] map;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    static int ans;
    static int mapRow;
    static int mapCol;

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

        ans = 0;
        map = new char[12][6];

        mapRow = map.length;
        mapCol = map[0].length;

        char[] line = null;
        for (int r = 0; r < mapRow; r++) {
            line = br.readLine().toCharArray();
            for (int c = 0; c < mapCol; c++) {
                map[r][c] = line[c];
            }
        }
		
        //pang() true -> 4개 모인게 존재해서, 다 터뜨리기까지 했다는 뜻
        while (pang()) {
            fallDown();
            ans++;
        }

        System.out.println(ans);
    }
	
    //터뜨리고 나서 블록을 밑으로 내리는 함수
    private static void fallDown() {
        for (int c = 0; c < mapCol; c++) {
            for (int sr = mapRow - 1; sr >= 0; sr--) {
                if (map[sr][c] == '.') {
                    for (int nr = sr - 1; nr >= 0; nr--) {
                        if (map[nr][c] != '.') {
                            map[sr][c] = map[nr][c];
                            map[nr][c] = '.';
                            break;
                        }
                    }
                }
            }
        }
    }

    //터뜨릴 게 있는지 확인
    private static boolean pang() {
        boolean flag = false;

        for (int r = 0; r < mapRow; r++) {
            for (int c = 0; c < mapCol; c++) {
                if (map[r][c] == '.') continue;
			
            	//모인 블록의 갯수가 4개면
                if (check(r, c) >= 4) {
                    //해당 블록들을 터뜨린다('.'으로 만드는 함수 수행)
                    boom(r, c, map[r][c]);
                    flag = true;
                }
            }
        }

        return flag;
    }

    //블록을 터뜨리는 함수('.'으로 만드는 함수)
    private static void boom(int sr, int sc, char color) {
        Queue<Puyo> q = new LinkedList<>();

        map[sr][sc] = '.';
        q.offer(new Puyo(sr, sc));

        while (!q.isEmpty()) {
            Puyo now = q.poll();

            for (int d = 0; d < 4; d++) {
                int nr = now.r + dr[d];
                int nc = now.c + dc[d];
                if (nr >= mapRow || nr < 0 || nc >= mapCol || nc < 0) {
                    continue;
                }

                if (map[nr][nc] == color) {
                    map[nr][nc] = '.';
                    q.offer(new Puyo(nr, nc));
                }
            }
        }
    }

    //유색블록의 상, 하, 좌, 우에 똑같은 색의 블록이 몇 개가 있는지 찾는 함수
    private static int check(int sr, int sc) {
        int cnt = 1;
        Queue<Puyo> q = new LinkedList<>();
        boolean[][] visited = new boolean[mapRow][mapCol];

        q.offer(new Puyo(sr, sc));
        visited[sr][sc] = true;

        while (!q.isEmpty()) {
            Puyo now = q.poll();

            for (int d = 0; d < 4; d++) {
                int nr = now.r + dr[d];
                int nc = now.c + dc[d];
                if (nr >= mapRow || nr < 0 || nc >= mapCol || nc < 0 || visited[nr][nc]) {
                	continue;
                }

                if (map[nr][nc] == map[sr][sc]) {
                    cnt++;
                    q.offer(new Puyo(nr, nc));
                    visited[nr][nc] = true;
                }
            }
        }

        return cnt;
    }
}

class Puyo {
    int r, c;

    Puyo(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

느낀점

어떻게 풀지 감도 안잡혔고, 답을 봐도 잘 이해가 안갔다. 하나하나 디버깅을 하고 나서야 감이 좀 잡혔다.
보아하니 이런 종류의 문제가 자주 출제되는 것 같았다. 프로그래머스에서 찾아보니까 2018년에 카카오 블라인드채용에서도 똑같은 문제가 출제되었었다. 답 얼른 외우고 그 문제는 혼자 다시 풀어봐야겠다.

[참고한 곳]
https://velog.io/@hyeon930/BOJ-11559-Puyo-Puyo-Java