반응형
11-13 12:44
Today
Total
«   2024/11   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
관리 메뉴

개발하는 고라니

[백준] 16768번 : Mooyo Mooyo 본문

Programming/백준

[백준] 16768번 : Mooyo Mooyo

조용한고라니 2021. 5. 8. 03:25
반응형
 

16768번: Mooyo Mooyo

In the example above, if $K = 3$, then there is a connected region of size at least $K$ with color 1 and also one with color 2. Once these are simultaneously removed, the board temporarily looks like this: 0000000000 0000000300 0054000300 1054500030 220000

www.acmicpc.net


[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);
    }
}
반응형

'Programming > 백준' 카테고리의 다른 글

[백준] 1034번 : 램프  (0) 2021.05.10
[백준] 9655번 : 돌 게임  (0) 2021.05.10
[백준] 17244번 : 아맞다우산  (0) 2021.05.06
[백준] 12886번 : 돌 그룹  (0) 2021.05.02
[백준] 14950번 : 정복자  (0) 2021.05.02
Comments