[Java] 백준 21609번 : 상어 중학교

문제

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

21609번: 상어 중학교

 

 

풀이 과정

가장 왼쪽, 위쪽에서 출발해서 일반 블럭일 때만 DFS 탐색을 하면, 일반블럭이 무조건 1개 이상인 조건을 만족한다.

탐색 후, (블럭 사이즈가 최대) || (이전 블럭 사이즈와 같고 rainbow블럭의 개수가 같거나 큼)일 때, 가장 큰 블럭 값을 갱신해준다.

가장 큰 블럭은 삭제하면서 -2로 표시한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    
    static int N, M;
    static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
    static int[][] map;

    static class Block{
        int rainbowCnt = 0;
        ArrayList<int[]> pos = new ArrayList<>();
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //
        int score = 0;
        while(true){
            //init
            Block bigBlock = new Block();
            bigBlock.pos.add(new int[]{0, 0});
            bigBlock.pos.add(new int[]{0, 0});
            bigBlock.rainbowCnt = -1;
            boolean[][] visited = new boolean[N][N];
            //simulation
            //1.
            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    if(visited[i][j] || map[i][j] <= 0){ continue;}
                    Block block = new Block();
                    dfs(i, j, map[i][j], visited, block);
                    int size = block.pos.size();
                    //rainbow는 방문 체크 제거
                    for(int[] pos : block.pos){
                        if(map[pos[0]][pos[1]] == 0) {
                            block.rainbowCnt++;
                            visited[pos[0]][pos[1]] = false;
                        }
                    }
                    if(size > bigBlock.pos.size() || (size == bigBlock.pos.size() && block.rainbowCnt >= bigBlock.rainbowCnt)){
                        bigBlock = block;
                    }
                    

                }
            }
            //블럭이 없다면 종료
            if(bigBlock.rainbowCnt == -1){
                break;
            }
            //2. 점수 추가 & 찾은 블럭 제거
            score += Math.pow(bigBlock.pos.size(), 2);
            for(int[] now : bigBlock.pos){
                map[now[0]][now[1]] = -2;
            }

            //3. 중력
            goDown();

            //4. 반시계방향 회전
            turnLeft();

            //5. 중력
            goDown();
        }
        System.out.println(score);
    }

    public static void dfs(int x, int y, int color, boolean[][] visited, Block block){
        visited[x][y] = true;
        block.pos.add(new int[]{x, y});

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || nx>=N || ny<0 || ny>=N || visited[nx][ny] || map[nx][ny] < 0){continue;}
            if(map[nx][ny] == color || map[nx][ny] == 0){
                dfs(nx, ny, color, visited, block);
            }
        }
    }

    public static void goDown(){
        for(int j=0; j<N; j++){
            for(int i=N-2; i>=0; i--){
                if(map[i][j] < 0){ continue;}
                int idx = i+1;
                while(idx<N && map[idx][j] < -1){
                    map[idx][j] = map[idx-1][j];
                    map[idx-1][j] = -2;
                    idx++;
                }
            }
        }
    }

    public static void turnLeft(){
        int[][] next = new int[N][N];
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                next[i][j] = map[j][(N-1-i)];
            }
        }
        map = next;
    }

}

 

 

결과