[백준] 16768번 : Mooyo Mooyo

16768번: Mooyo Mooyo

---

[DFS]

뿌요뿌요(?)와 비슷한 방식의 게임이라고 하며, 0은 빈 칸이고, 1~9로 이루어진 각각 다른 색의 세포가 10 x N 격자에 있는데 최소 K개의 같은 색인 인접(상하좌우)한 세포가 있으면 그 덩어리는 사라지며 빈 공간으로 변경되고, 위의 애들이 중력에 의해 내려오고, 다시 터지고 내려오고를 반복해 더이상 터지지 않을 때 까지 반복하는 문제이다.

 

맨 아랫줄부터 DFS 탐색하며 탐색하는 정점마다 Stack에 저장하고 같은 색의 인접한 칸이 K개 이상이면 DFS를 마치고 Stack에 저장된 좌표의 값을 0(빈 공간)으로 만들어준다.

//DFS
    static void DFS(int y, int x, int value){

        cnt++;
        visit[y][x] = true;
        stack.push(new Point(y, x));

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

            if(ny < 1 || nx < 1 || ny > n || nx > 10 || visit[ny][nx] || map[ny][nx] != value) continue;

            DFS(ny, nx, value);
        }
    }

//main 일부
        while(true){
            visit = new boolean[101][11];
            boolean flag = false;

            downward();
            
            for(int i=n; i>0; i--)
                for(int j=1; j<=10; j++){
                
                    if(visit[i][j] || map[i][j] == 0) continue;
                    
                    stack.clear();
                    cnt = 0;
                    
                    DFS(i, j, map[i][j]);

                    if(cnt >= k) {
                        flag = true;
                        for (Point p : stack)
                            map[p.y][p.x] = 0;
                    }
                }

            if(!flag) break;
        }

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    static class Point {
        int y, x;
        public Point(int yy, int xx){
            y=yy;
            x=xx;
        }
    }

    static Stack<Point> stack = new Stack<>();
    static int n, k, cnt;
    static int[] Y = {-1,1,0,0}, X = {0,0,-1,1};
    static int[][] map = new int[101][11];
    static boolean[][] visit;

    static void downward(){

        for(int i=n-1; i > 0; i--)
            for(int j=1; j<=10; j++) {
                //현재 정점이 0 또는 아래 정점이 !0
                if (map[i][j] == 0 || map[i + 1][j] != 0) continue;

                int z = i+1;
                while(z <= n && map[z][j] == 0){
                    map[z][j] = map[z-1][j];
                    map[z-1][j] = 0;
                    z++;
                }
            }
    }
    static void DFS(int y, int x, int value){

        cnt++;
        visit[y][x] = true;
        stack.push(new Point(y, x));

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

            if(ny < 1 || nx < 1 || ny > n || nx > 10 || visit[ny][nx] || map[ny][nx] != value) continue;

            DFS(ny, nx, value);
        }
    }

    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());

        for(int i=1; i<=n; i++){
            char[] str = br.readLine().toCharArray();
            for(int j=1; j<=10; j++)
                map[i][j] = str[j-1] - '0';
        }

        while(true){
            visit = new boolean[101][11];
            boolean flag = false;

            downward();
            for(int i=n; i>0; i--)
                for(int j=1; j<=10; j++){
                    if(visit[i][j] || map[i][j] == 0) continue;
                    stack.clear();
                    cnt = 0;
                    DFS(i, j, map[i][j]);

                    if(cnt >= k) {
                        flag = true;
                        for (Point p : stack)
                            map[p.y][p.x] = 0;
                    }
                }

            if(!flag) break;
        }

        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=n; i++){
            for(int j=1; j<=10; j++)
                sb.append(map[i][j]);
            sb.append('\n');
        }
        System.out.print(sb);
    }
}