백준 21609번: 상어 중학교 (Java)

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

21609번: 상어 중학교

 

 

 

 

 

 

 

 

---

 

풀이

1. 블록 기록

빈 칸은 -2로 표현하였습니다.

 

2. 블록 그룹

Blocks 라는 class를 만들어 (블록의 수, 무지개 블록의 수, 행, 열)을 저장하였으며, 블록의 수 -> 무지개 블록의 수 -> 행 -> 열 크기로 비교할 수 있게 Comparable을 implement했습니다.

 

3. 시뮬레이션

3-1. 가장 큰 블록 그룹 찾기

 - 블록 그룹의 위치값은 '일반 블록의 가장 위/왼쪽 행, 열'로 정의됩니다. 이는 일반적인 for문으로 순회하면 자연스럽게 처리됩니다.

 - BFS로 찾는데, 한 블록 그룹을 찾을 때마다 (처음 블록의 색깔) or (무지개 색깔) 블록을 방문처리하여 방문합니다. 그러나, 무지개 색깔 블록은 다른 블록 그룹을 만드는데도 사용 가능하므로, BFS가 끝난 이후 무지개 색깔 블록 방문처리를 초기화합니다.

3-2 터뜨리기

 - 똑같이 BFS로 처리합니다. 3-1에서 작성한 코드를 복사하여 일부분만 사용합니다.

3-3 중력

 - 물건을 떨어뜨리는 행(시작점), 물건이 떨어지는 행(도착점)을 나누어 관리합니다.

 - 떨어뜨리는 위치에 있는 물건이 블록 / 검은색 블록 / 빈 칸인지에 따라 다르게 대응하면 됩니다.

3-4 회전

 - (i, j) <- (j, N-1-i) 끝

 

구현 종합 선물 세트입니다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };
    static final int BLANK = -2, BLACK = -1, RAINBOW = 0;
    static int[][] map;
    static int N, M, ans = 0;
    static boolean[][] visited;
    static Blocks b;
    
    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());
        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());
            }
        }
        
        while (true) {
            b = new Blocks(0, 0, 0, 0);
            visited = new boolean[N][N];
            // 블록 그룹들 찾기
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] > 0 && !visited[i][j]) {
                        bfs(i, j);
                    }
                }
            }
            // 최대 크기의 블록이 2개 미만이라면: 끝
            if (b.num < 2) break;
            ans += b.num * b.num;
            // 최대 블록 터뜨리기
            blockPop(b.row, b.col);
            gravity();
            rotate();
            gravity();
        }
        System.out.println(ans);
    }
    
    // (i, j)열 블록 그룹의 (블록 수, 무지개 블록 수, i, j)를 구하는 method
    static void bfs(int i, int j) {
        int block = map[i][j];
        visited[i][j] = true;
        int cnt = 1;
        int rainbowCnt = 0;
        Queue<int[]> queue = new ArrayDeque<>();
        Queue<int[]> rainbowQueue = new ArrayDeque<>();
        queue.offer(new int[] {i, j});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                // 방문했거나, 무지개 색이나 현재 블록 색이랑 다르면 방문 ㄴㄴ
                if (visited[nr][nc] || (map[nr][nc] != RAINBOW && map[nr][nc] != block)) continue;
                if (map[nr][nc] == RAINBOW) {
                    rainbowQueue.add(new int[] {nr, nc});
                    rainbowCnt++;
                }
                visited[nr][nc] = true;
                queue.offer(new int[] {nr, nc});
                cnt++;
            }
        }
        
        // 무지개 블록은 여로 블록 그룹에 포함될 수 있음: visited 처리 초기화
        while (!rainbowQueue.isEmpty()) {
            int[] cur = rainbowQueue.poll();
            int r = cur[0], c = cur[1];
            visited[r][c] = false;
        }
        
        Blocks tempBlock = new Blocks(cnt, rainbowCnt, i, j);
        // 현재 찾은 블록 그룹이 최댓값이라면 변경
        if (tempBlock.compareTo(b) > 0) b = tempBlock;
    }
    
    // 최대 블록 그룹을 터뜨리는 method
    static void blockPop(int i, int j) {
        int block = map[i][j];
        map[i][j] = BLANK;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] {i, j});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int r = cur[0], c = cur[1];
            for (int k = 0; k < 4; k++) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                if (map[nr][nc] != RAINBOW && map[nr][nc] != block) continue;
                map[nr][nc] = BLANK;
                queue.offer(new int[] {nr, nc});
            }
        }
    }
    
    // 중력을 적용하는 method
    // x: 떨어지는 블록 시작점, y: 떨어지는 블록 도착점
    static void gravity() {
        for (int j = 0; j < N; j++) {
            int y = N-1;
            for (int x = N-1; x >= 0; x--) {
                // 블록이 있는 경우:
                if (map[x][j] >= 0) {
                    // 위치가 다른 경우: x에서 y로 떨어질 예정
                    if (x < y) {
                        map[y][j] = map[x][j];
                        map[x][j] = BLANK;
                        y--;
                    // x == y인 경우: 해당 블록은 땅에 닿아있으며, 그 위가 떨어질 위치가 된다.
                    } else {
                        y--;
                    }
                } else if (map[x][j] == BLACK) y = x-1;
            }
        }
    }
    
    // 반시계로 90도 돌리는 method
    static void rotate() {
        int[][] tempMap = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                tempMap[i][j] = map[j][N-1-i];
            }
        }
        map = tempMap;
    }
    
    // 블록 그룹을 정의하는 class: (블록 수, 무지개 블록 수, 행, 열)
    static class Blocks implements Comparable<Blocks> { 
        int num;
        int rainbowNum;
        int row;
        int col;
        
        public Blocks(int num, int rainbowNum, int row, int col) {
            this.num = num;
            this.rainbowNum = rainbowNum;
            this.row = row;
            this.col = col;
        }
 
        public String toString() {
            return "Blocks [num=" + num + ", row=" + row + ", col=" + col + "]";
        }
 
        public int compareTo(Blocks o) {
            if (this.num == o.num) {
                if (this.rainbowNum == o.rainbowNum) {
                    if (this.row == o.row) {
                        return this.col - o.col;
                    }
                    return this.row - o.row;
                }
                return this.rainbowNum - o.rainbowNum;
            }
            return this.num - o.num;
        }
    }
    
    // 디버깅용 method
    static void printMap() {
        for (int i = 0; i < N; i++) {
            System.out.println(Arrays.toString(map[i]));
        }
        System.out.println("*******************");
    }
}