[백준] 11559번 : Puyo Puyo

11559번: Puyo Puyo

---

[BFS]

main에서 하는 일은 단 4가지다.

1) visit 초기화

2) 맵 BFS로 스캔 하며 터트릴 것이 있다면 터트리고, flag = true로 설정(flag == false면 종료 시퀀스)

3) score++

4) 블록들을 아래로 내려주는 down()

 

다시 1~4 반복.

 

2) 에서 Queue를 이용해 BFS를 구현하였고, 큐에 들어가는 좌표를 List에 담아 만약 4개 이상 담겼다면 터트리고 마지막에 List를 초기화시켰다.

 

# Code </>

public class Main {

    static class Point{
        int y, x;
        public Point(int yy, int xx){
            y=yy; x=xx;
        }
    }
    static final int r = 13, c = 7;
    static char[][] map = new char[r][c];
    static boolean[][] visit;
    static int[] Y = {-1, 1, 0, 0}, X = {0, 0, -1, 1};

    static boolean BFS(){

        Queue<Point> q = new LinkedList<>();
        List<Point> list = new ArrayList<>();
        boolean flag = false;

        for(int i=1; i<r; i++)
            for(int j=1; j<c; j++){
                char current = map[i][j];
                int size = 1;

                if(!visit[i][j] && current != '.'){
                    list.add(new Point(i, j));
                    current = map[i][j];
                    visit[i][j] = true;
                    q.add(new Point(i, j));
                }

                while(!q.isEmpty()){
                    Point p = q.poll();

                    for(int a=0; a<4; a++){
                        int ny = p.y+Y[a];
                        int nx = p.x+X[a];

                        if(ny < 1 || nx < 1 || ny > r-1 || nx > c-1 || visit[ny][nx] || map[ny][nx] != current) continue;

                        visit[ny][nx] = true;
                        size++;
                        list.add(new Point(ny, nx));
                        q.add(new Point(ny, nx));
                    }
                }

                if(size >= 4) {
                    flag = true;
                    for (Point p : list)
                        map[p.y][p.x] = '.';
                }

                list.clear();
            }



        return flag;
    }
    static void down(){

        Queue<Point> Q = new LinkedList<>();

        for(int i=r-2; i>0; i--)
            for(int j=1; j<c; j++) {
                if (map[i][j] != '.')
                    Q.add(new Point(i, j));

                while(!Q.isEmpty()){
                    Point p = Q.poll();

                    char tmp = map[p.y][p.x];
                    int ny = p.y+1;
                    if(ny > r-1 || map[ny][p.x] != '.') continue;

                    map[p.y][p.x] = '.';
                    map[ny][p.x] = tmp;
                    Q.add(new Point(ny, p.x));
                }
            }
    }

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

        for(int i=1; i<r; i++){
            char[] arr = br.readLine().toCharArray();
            for(int j=1; j<c; j++)
                map[i][j] = arr[j-1];
        }

        int score = 0;
        while(true){
            visit = new boolean[r][c];
            
            if(!BFS()) break;
            
            score++;
            down();
        }
        System.out.println(score);
    }
}

......
......
......
......
......
......
......
......
.Y....
.YG...
RRYG..
RRYGG.

-------------
......
......
......
......
......
......
......
......
......
..G...
.YYG..
.YYGG.
-------------
......
......
......
......
......
......
......
......
......
......
...G..
..GGG.
-------------
......
......
......
......
......
......
......
......
......
......
......
......
-------------
3