[백준/Java] 21609 상어 중학교

🔗 문제 링크: https://www.acmicpc.net/problem/21609

🔍 해결 과정

이 문제는 시뮬레이션 문제로 시간 초과 걱정할 필요 없이 조건에 맞춰 문제를 해결하면 됩니다. 개인적으로 코드를 작성하는 과정에 있어서 디버깅 등의 시간도 할애하느라 시간을 많이 썼던 문제였습니다. 처음에 문제를 보고 핵심 조건에 맞춰서 그에 맞는 메서드를 분류했습니다. 핵심 기능들은 다음과 같습니다.

1️⃣ 크기가 가장 큰 블록 그룹을 찾는 기능
2️⃣ 기준 블록이 속한 블록 그룹에 있는 블록들을 제거하는 기능 (제거하면서 점수를 반환한다.)
3️⃣ 중력 작용 기능
4️⃣ 90도 반시계 방향 회전 기능

 

메인 함수에서는 위와 같이 4개의 핵심 기능들을 정의하였고, 조건에 맞춰서 핵심 기능들을 구현하는 방향으로 문제를 해결하였습니다. 

 

---

✏️ 코드

import java.io.*;
import java.util.*;

class Pair {
    private final int x;
    private final int y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

public class Main {


    private static final String SPACE = " ";

    private static final int INF = (int) 1e9;
    private static final int BLACK = -1;
    private static final int RAINBOW = 0;

    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[][] board = new int[n][n];
        int[] maxBlockInfo;
        int totalScore = 0;

        for (int i = 0; i < n; ++i) {
            board[i] = Arrays.stream(br.readLine().split(SPACE))
                    .mapToInt(Integer::parseInt)
                    .toArray();
        }

	// 핵심 기능들 정의
        while (hasBlockGroup(board, n)) { // 블록 그룹이 없어질 때까지 반복
            maxBlockInfo = findMaxBlockGroup(board, n); // {큰 그룹의 블록 개수, 큰 그룹의 기준행, 큰 그룹의 기준열} 반환
            totalScore += removeBlockGroup(board, n, maxBlockInfo); // 블록 제거하면서 점수 반환(제거한 자리는 INF로 대체)
            gravity(board, n); // 중력 작용
            counterClockWise90(board, n); // 반시계 방향 회전
            gravity(board, n); // 중력 작용
        }

        bw.write(Integer.toString(totalScore));
        bw.flush();
        bw.close();
    }

    private static boolean hasBlockGroup(final int[][] board,
                                         final int n) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (isGeneralBlock(board, i, j)) { // 일반 블록이라면
                    int blockNumber = board[i][j];

                    for (int dir = 0; dir < 4; ++dir) {
                        int nx = i + dx[dir];
                        int ny = j + dy[dir];

			// 블록 그룹은 블록이 2개 이상 있어야 된다.
                        if (validGroup(board, n, blockNumber, nx, ny)) {
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    private static boolean validGroup(int[][] board, int n, int blockNumber,
                                      int nx, int ny) {
        return !(nx < 0 || ny < 0 || nx >= n || ny >= n) &&
                (board[nx][ny] == blockNumber || board[nx][ny] == RAINBOW);
    }

    private static int[] findMaxBlockGroup(final int[][] board,
                                           final int n) {
        boolean[][] visited = new boolean[n][n];

        int maxBlockCount = 0;
        int rainbowCount = 0;
        int standardRow = -1;
        int standardCol = -1;

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (!isGeneralBlock(board, i, j) || visited[i][j]) {
                    continue;
                }

                int[] blockCountInfo = bfs(board, n, visited, i, j);

                if (blockCountInfo[0] == maxBlockCount) {
                    if (blockCountInfo[1] == rainbowCount) {
                        if (blockCountInfo[2] == standardRow) {
                            if (blockCountInfo[3] > standardCol) {
                                standardCol = blockCountInfo[3];
                            }
                        } else if (blockCountInfo[2] > standardRow) {
                            standardRow = blockCountInfo[2];
                            standardCol = blockCountInfo[3];
                        }
                    } else if (blockCountInfo[1] > rainbowCount) {
                        rainbowCount = blockCountInfo[1];
                        standardRow = blockCountInfo[2];
                        standardCol = blockCountInfo[3];
                    }
                } else if (blockCountInfo[0] > maxBlockCount) {
                    maxBlockCount = blockCountInfo[0];
                    rainbowCount = blockCountInfo[1];
                    standardRow = blockCountInfo[2];
                    standardCol = blockCountInfo[3];
                }
            }
        }

        return new int[]{maxBlockCount, standardRow, standardCol};
    }

    private static int[] bfs(int[][] board, final int n,
                             boolean[][] visited, int r, int c) {
        int totalCount = 1;
        int rainbowCount = 0;
        Queue<Pair> q = new ArrayDeque<>();
        visited[r][c] = true;
        q.offer(new Pair(r, c));
        int blockNumber = board[r][c];
        List<Pair> rainbows = new ArrayList<>();

        while (!q.isEmpty()) {
            Pair pair = q.poll();
            int x = pair.getX();
            int y = pair.getY();

            for (int dir = 0; dir < 4; ++dir) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];

                if (!valid(board, visited, n, blockNumber, nx, ny)) {
                    continue;
                }

                ++totalCount;

                if (board[nx][ny] == RAINBOW) {
                    rainbows.add(new Pair(nx, ny));
                    ++rainbowCount;
                }

                q.offer(new Pair(nx, ny));
                visited[nx][ny] = true;
            }
        }

        for (Pair rainbow : rainbows) {
            visited[rainbow.getX()][rainbow.getY()] = false;
        }

        return new int[]{totalCount, rainbowCount, r, c};
    }

    private static boolean valid(final int[][] board, final boolean[][] visited,
                                 final int n, final int blockNumber, final int nx, final int ny) {
        return !(nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) &&
                (board[nx][ny] == blockNumber || board[nx][ny] == RAINBOW);
    }

    private static int removeBlockGroup(final int[][] board,
                                        final int n, final int[] maxBlockInfo) {
        boolean[][] visited = new boolean[n][n];
        Queue<Pair> q = new ArrayDeque<>();
        q.offer(new Pair(maxBlockInfo[1], maxBlockInfo[2]));
        visited[maxBlockInfo[1]][maxBlockInfo[2]] = true;
        int blockNumber = board[maxBlockInfo[1]][maxBlockInfo[2]];
        board[maxBlockInfo[1]][maxBlockInfo[2]] = INF;

        while (!q.isEmpty()) {
            Pair pair = q.poll();
            int x = pair.getX();
            int y = pair.getY();

            for (int dir = 0; dir < 4; ++dir) {
                int nx = x + dx[dir];
                int ny = y + dy[dir];

                if (!valid(board, visited, n, blockNumber, nx, ny)) {
                    continue;
                }

                board[nx][ny] = INF;
                visited[nx][ny] = true;
                q.offer(new Pair(nx, ny));
            }
        }
        return maxBlockInfo[0] * maxBlockInfo[0];
    }

    private static void gravity(final int[][] board,
                                final int n) {
        for (int c = 0; c < n; ++c) {
            for (int r = n - 1; r >= 0; --r) {
                if (board[r][c] != INF) {
                    continue;
                }

                int rTemp = r - 1;

                while (rTemp >= 0 && board[rTemp][c] == INF) {
                    --rTemp;
                }

                if (rTemp < 0) {
                    break;
                }

                if (board[rTemp][c] == BLACK) {
                    r = rTemp;
                    continue;
                }

                swap(board, rTemp, r, c);
            }
        }
    }

    private static void swap(int[][] board, int rTemp, int r, int c) {
        int temp = board[rTemp][c];
        board[rTemp][c] = board[r][c];
        board[r][c] = temp;
    }

    private static void counterClockWise90(final int[][] board,
                                           final int n) {
        int[][] boardTemp = new int[n][n];
        for (int i = 0; i < n; ++i) {
            boardTemp[i] = board[i].clone();
        }

        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < n; ++c) {
                board[r][c] = boardTemp[c][n - 1 - r];
            }
        }
    }

    private static boolean isGeneralBlock(final int[][] board, final int r, final int c) {
        return board[r][c] != INF && board[r][c] != BLACK &&
                board[r][c] != RAINBOW;
    }
}