백준 11559번 Puyo Puyo

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

public class Puyo_Puyo {
    static char[][] map;
    static int[] dr = {1,0,-1,0};
    static int[] dc = {0,1,0,-1};
    static boolean flag = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str;
        int answer = 0;
        map = new char[12][6];
        for (int i = 0; i < 12; i++) {
            str = br.readLine();
            for (int j = 0; j < 6; j++) {
                map[i][j] = str.charAt(j);

            }
        }
        while(true) {
            for (int i = 0; i < 12; i++) {
                for (int j = 0; j < 6; j++) {
                    if (map[i][j]!='.') {
                        bfs(i, j);
                    }
                }
            }
            if (flag) {//연쇄가 일어났으면 +1 안일어나면 끝
                answer++;
                flag = false;
                move();
            }
            else {
                break;
            }
//            for (int i = 0; i < 12; i++) {
//                for (int j = 0; j < 6; j++) {
//                    System.out.print(map[i][j] +" ");
//                }
//                System.out.println();
//            }
//            System.out.println();
        }
        System.out.println(answer);


    }
    public static void move(){
        for (int i = 10; i >=0 ; i--) {
            for (int j = 0; j < 6; j++) {
                if(map[i][j]=='.')
                    continue;
                if(map[i+1][j]=='.'){
                    int a = i;
                    while(true){
                        if(a==11)
                            break;
                        if(map[a+1][j]=='.') {
                            map[a + 1][j] = map[a][j];
                            map[a][j] = '.';
                            a++;
                        }
                        else
                            break;
                    }

                }

            }
        }
    }
    public static void bfs(int row, int col){
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{row,col});
        List<int[]> list = new ArrayList<>();
        boolean[][] visited = new boolean[12][6];
        int count = 0;
        while (!que.isEmpty()){
            int[] current = que.poll();
            int crow = current[0];
            int ccol = current[1];

            for (int i = 0; i < 4; i++) {
                int nrow = crow + dr[i];
                int ncol = ccol + dc[i];
                if(nrow<0||ncol<0||nrow>=12||ncol>=6)
                    continue;
                if(visited[nrow][ncol])
                    continue;
                if(map[nrow][ncol] != '.' && (map[nrow][ncol]== map[crow][ccol])){
                    count++;
                    list.add(new int[]{nrow,ncol});
                    que.add(new int[] {nrow,ncol});
                    visited[nrow][ncol] = true;
                }

            }
        }
        if(count>=4){
            flag = true; //연쇄 일어남
            for (int j = 0; j < list.size(); j++) {
                int r = list.get(j)[0];
                int c = list.get(j)[1];
                map[r][c] = '.';
            }
        }
    }
}

풀이방법

📢문제를 보면 닿아있는 블럭은 연쇄가 일어나므로, bfs를 써야 한다는것을 떠올릴 수 있으며, bfs후 맵 이동, 이런방식으로 설계를 한다.

1. 입력을 넣고 맵을 처음부터 탐색하면서 문자를 만나면 해당문자와 연결된칸을 없애는 bfs를 시작한다.
2. bfs함수 내에서는 해당하는 문자와 같은 문자일때만 que에 넣고, 인덱스를 list에 담는다..
3. 칸의 갯수를 하나식 세서, 4개이상이라면 연쇄작용을 통해 맵에서 '.'으로 대체하고, 연쇄가 일어났다는 체크를 하기위해 flag로 표시하였다.
4. 이를 반복하면서 하나의 연쇄작용시 일어날 수 있는 연쇄를 모두 수행한다.
5. 연쇄가 일어났다면 이제 맵을 이동시킨다.
6. 아래행에서 부터 순차적으로 떨어져야하므로 역순으로 map을 탐색한다.
7. 떨어지다가 문자를 만날 때 또는 행의 마지막까지 떨어지도록 반복해준다.
8. 연쇄가 일어나지 않을때까지 반복한다.

후기

bfs에 여러 조건이 달려있어 생각해내기 까다로운 문제였던것 같다.
또 이동하는 조건도 맵에 끝까지 이동해야 하는점도 쉽지 않았던 문제였다.