Notice

Recent Posts

Recent Comments

Link

Github

« 2025/09 »
일	월	화	수	목	금	토
	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

Tags more

Archives

Today

Total

관리 메뉴

NullNull

[백준 P21609] 상어 중학교 Java 본문

알고리즘

[백준 P21609] 상어 중학교 Java

KYBee 2022. 9. 19. 20:50

P21609 상어 중학교

21609번: 상어 중학교

상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록

www.acmicpc.net

문제

상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다.

블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다. 블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.

오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.

크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B^2점을 획득한다.
격자에 중력이 작용한다.
격자가 90도 반시계 방향으로 회전한다.
다시 격자에 중력이 작용한다.

격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.

오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.

입력값

첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.

둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.

1 ≤ N ≤ 20
1 ≤ M ≤ 5

출력값

첫째 줄에 획득한 점수의 합을 출력한다.

알고리즘

전형적인 구현 문제이다. 구현 문제를 풀 때는 문제를 풀기 전에 해야하는 일들을 리스팅하고 풀이를 시작한다. 해당 문제를 풀기 위해서 해야 하는 일들은 다음과 같다.

크기가 가장 큰 블록 그룹을 찾는다.
1에서 찾는 그룹의 모든 블록을 제거한다. 점수를 업데이트한다.
격자에 중력을 작용시킨다.
90도 반시계 방향으로 회전한다.
격자에 중력을 작용시킨다.

블록 그룹을 저장할 클래스를 하나 선언한다. 블록 클래스에는 기준점의 행과 열, 무지개 블록의 수, 블록의 수를 기록한다. 기준점의 행과 열, 무지개 블록의 수는 가장 큰 블록을 찾기 위해 기록하는 변수이고, 블록의 수는 점수를 얻기 위해 저장하는 변수이다.

class Block implements Comparable<Block> {
    int startR, startC, cnt, rainbow;

    Block(int startR, int startC, int cnt, int rainbow) {
        this.startR = startR;
        this.startC = startC;
        this.cnt = cnt;
        this.rainbow = rainbow;
    }

    @Override
    public String toString() {
        return "Block{" +
                "startR=" + startR +
                ", startC=" + startC +
                ", cnt=" + cnt +
                ", rainbow=" + rainbow +
                '}';
    }

    @Override
    public int compareTo(Block b) {
        int comp = Integer.compare(b.cnt, cnt);
        if (comp == 0) {
            comp = Integer.compare(b.rainbow, rainbow);
        }
        if (comp == 0) {
            comp = Integer.compare(b.startR, startR);
        }
        if (comp == 0) {
            comp = Integer.compare(b.startC, startC);
        }
        return comp;
    }
}

맵을 탐색하면서 가능한 블록들을 넣는 역할을 하는 findBlock 메서드를 구현했다. 여기서 중요한 점은 무지개 블록의 경우에는 여러개의 블록 그룹에 속할 수 있다는 점이다. 따라서 방문을 기록할 방문 배열을 하나 선언해서 운용하면서 rainbows라는 큐를 추가로 사용한다. bfs로 맵을 탐색하면서 발견한 블록 그룹을 block 객체로 만들어주면 되는데 이때 하나의 블록 그룹을 발견하면 그 블록 내에 존재하는 무지개 블록은 다시 방문 처리를 해제해준다. 이 방법으로 다른 그룹에서도 이전에 사용했던 무지개 블록에 방문할 수 있도록 했다. 또한 시작점이 무지개 블록인 경우에는 따로 탐색을 진행하지 않는다.

public static void findBlock() {
    boolean[][] visited = new boolean[N][N];
    Queue<int[]> q = new ArrayDeque<>();
    Queue<int[]> rainbows = new ArrayDeque<>();

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            // 안가봤고 무지개가 아닐 때 만 간다
            if (!visited[i][j] && map[i][j] != M + 1 && map[i][j] != -1 && map[i][j] != 0) {
                visited[i][j] = true;
                q.add(new int[] {i, j});
                int rainbowCnt = 0;
                int startR = i;
                int startC = j;
                int totalCnt = 1;

                while (!q.isEmpty()) {
                    int[] current = q.poll();
                    int curR = current[0];
                    int curC = current[1];

                    for (int d = 0; d < 4; d++) {
                        int newR = curR + dr[d];
                        int newC = curC + dc[d];

                        if (0 <= newR && newR < N && 0 <= newC && newC < N && !visited[newR][newC]) {
                            if (map[newR][newC] == map[i][j]) {
                                visited[newR][newC] = true;
                                totalCnt++;
                                q.add(new int[] {newR, newC});
                            } else if (map[newR][newC] == M + 1) {
                                rainbowCnt++;
                                rainbows.add(new int[] {newR, newC});

                                visited[newR][newC] = true;
                                totalCnt++;
                                q.add(new int[] {newR, newC});
                            }
                        }
                    }
                }

                // rainbow 방문을 다시 해제 -> 다른 색 공도 들어올 수 있도록
                while (!rainbows.isEmpty()){
                    int[] current = rainbows.poll();
                    visited[current[0]][current[1]] = false;
                }

                // block 새로 하나 만들기
                if (totalCnt < 2) continue;
                pq.add(new Block(startR, startC, totalCnt, rainbowCnt));
            }
        }
    }
}

가장 큰 블록을 찾기 위해서 블록을 PriorityQueue에 저장했다. 맵 탐색이 끝났다면 가장 큰 블록은 루트 노드에 있게 된다. 그 루트 노드에 있는 블록 그룹의 모든 블록을 제거하고 점수를 업데이트 한다.

deleteBlock(pq.peek());

public static void deleteBlock(Block target) {
    int r = target.startR;
    int c = target.startC;
    int color = map[r][c];
    answer += target.cnt * target.cnt;

    Queue<int[]> q = new ArrayDeque<>();
    map[r][c] = 0;
    q.add(new int[] {r, c});

    while(!q.isEmpty()) {
        int[] current = q.poll();
        int curR = current[0];
        int curC = current[1];

        for (int i = 0; i < 4 ; i++){
            int newR = curR + dr[i];
            int newC = curC + dc[i];

            if (0 <= newR && newR < N && 0 <= newC && newC < N && map[newR][newC] != 0 && map[newR][newC] != -1) {
                if (map[newR][newC] == M + 1 || map[newR][newC] == color) {
                    map[newR][newC] = 0;
                    q.add(new int[] {newR, newC});
                }
            }
        }
    }
}

이제 격자에 중력을 작용 시킵니다. 중력은 아래에서 위로 요소들을 하나씩 찾아보면서 만약 중력으로 떨어질 요소를 발견하면 이를 하나씩 배치할 수 있는 곳으로 배치하면서 로직을 수행합니다.

public static void gravity() {
    for (int i = 0; i < N; i++) {
        //한줄씩 검사
        for (int j = N - 1; j >= 0; j--) {
            if (map[j][i] != 0 && map[j][i] != -1) {
                int bottom = j + 1;

                while (true) {
                    if (bottom == N) break;

                    if (map[bottom][i] == 0) bottom++;
                    else break;
                }

                if (bottom == j + 1) continue;
                map[bottom - 1][i] = map[j][i];
                map[j][i] = 0;
            }
        }
    }
}

그리고 반시계 방향으로 요소를 회전하는 함수를 구현합니다. 배열 회전의 경우에는 인덱스 값을 잘 조절하면 쉽게 구현할 수 있습니다.

public static void rotate() {
    int[][] res = new int[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int newI = N - 1 - j;
            int newJ = i;
            res[newI][newJ] = map[i][j];
        }
    }

    map = res;
}

마지막으로 구현해둔 메서드들을 실행하면서 오토 플레이가 끝날때까지 돌립니다. 오토 플레이가 끝나면 획득한 점수의 합을 출력합니다.

코드

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

public class Main {
    static final int[] dr = {-1, 0, 1, 0};
    static final int[] dc = {0, -1, 0, 1};

    static int N;
    static int[][] map;
    static int M;
    static int answer;
    static PriorityQueue<Block> pq = new PriorityQueue<>();

    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());
                if (map[i][j] == 0) map[i][j] = M + 1;
            }
        }

        while(true) {
            findBlock();
            if (pq.size() == 0) break;

            deleteBlock(pq.peek());
            pq = new PriorityQueue<>();

            gravity();
            rotate();
            gravity();
        }

        System.out.println(answer);
    }

    public static void findBlock() {
        boolean[][] visited = new boolean[N][N];
        Queue<int[]> q = new ArrayDeque<>();
        Queue<int[]> rainbows = new ArrayDeque<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 안가봤고 무지개가 아닐 때 만 간다
                if (!visited[i][j] && map[i][j] != M + 1 && map[i][j] != -1 && map[i][j] != 0) {
                    visited[i][j] = true;
                    q.add(new int[] {i, j});
                    int rainbowCnt = 0;
                    int startR = i;
                    int startC = j;
                    int totalCnt = 1;

                    while (!q.isEmpty()) {
                        int[] current = q.poll();
                        int curR = current[0];
                        int curC = current[1];

                        for (int d = 0; d < 4; d++) {
                            int newR = curR + dr[d];
                            int newC = curC + dc[d];

                            if (0 <= newR && newR < N && 0 <= newC && newC < N && !visited[newR][newC]) {
                                if (map[newR][newC] == map[i][j]) {
                                    visited[newR][newC] = true;
                                    totalCnt++;
                                    q.add(new int[] {newR, newC});
                                } else if (map[newR][newC] == M + 1) {
                                    rainbowCnt++;
                                    rainbows.add(new int[] {newR, newC});

                                    visited[newR][newC] = true;
                                    totalCnt++;
                                    q.add(new int[] {newR, newC});
                                }
                            }
                        }
                    }

                    // rainbow 방문을 다시 해제 -> 다른 색 공도 들어올 수 있도록
                    while (!rainbows.isEmpty()){
                        int[] current = rainbows.poll();
                        visited[current[0]][current[1]] = false;
                    }

                    // block 새로 하나 만들기
                    if (totalCnt < 2) continue;
                    pq.add(new Block(startR, startC, totalCnt, rainbowCnt));
                }
            }
        }
    }

    public static void deleteBlock(Block target) {
        int r = target.startR;
        int c = target.startC;
        int color = map[r][c];
        answer += target.cnt * target.cnt;

        Queue<int[]> q = new ArrayDeque<>();
        map[r][c] = 0;
        q.add(new int[] {r, c});

        while(!q.isEmpty()) {
            int[] current = q.poll();
            int curR = current[0];
            int curC = current[1];

            for (int i = 0; i < 4 ; i++){
                int newR = curR + dr[i];
                int newC = curC + dc[i];

                if (0 <= newR && newR < N && 0 <= newC && newC < N && map[newR][newC] != 0 && map[newR][newC] != -1) {
                    if (map[newR][newC] == M + 1 || map[newR][newC] == color) {
                        map[newR][newC] = 0;
                        q.add(new int[] {newR, newC});
                    }
                }
            }
        }
    }

    public static void gravity() {
        for (int i = 0; i < N; i++) {
            //한줄씩 검사
            for (int j = N - 1; j >= 0; j--) {
                if (map[j][i] != 0 && map[j][i] != -1) {
                    int bottom = j + 1;

                    while (true) {
                        if (bottom == N) break;

                        if (map[bottom][i] == 0) bottom++;
                        else break;
                    }

                    if (bottom == j + 1) continue;
                    map[bottom - 1][i] = map[j][i];
                    map[j][i] = 0;
                }
            }
        }
    }

    public static void rotate() {
        int[][] res = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int newI = N - 1 - j;
                int newJ = i;
                res[newI][newJ] = map[i][j];
            }
        }

        map = res;
    }
}

class Block implements Comparable<Block> {
    int startR, startC, cnt, rainbow;

    Block(int startR, int startC, int cnt, int rainbow) {
        this.startR = startR;
        this.startC = startC;
        this.cnt = cnt;
        this.rainbow = rainbow;
    }

    @Override
    public String toString() {
        return "Block{" +
                "startR=" + startR +
                ", startC=" + startC +
                ", cnt=" + cnt +
                ", rainbow=" + rainbow +
                '}';
    }

    @Override
    public int compareTo(Block b) {
        int comp = Integer.compare(b.cnt, cnt);
        if (comp == 0) {
            comp = Integer.compare(b.rainbow, rainbow);
        }
        if (comp == 0) {
            comp = Integer.compare(b.startR, startR);
        }
        if (comp == 0) {
            comp = Integer.compare(b.startC, startC);
        }
        return comp;
    }
}

저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

[백준 P1717] 집합의 표현 Java (0)	2022.09.19
[백준 P17352] 여러분의 다리가 되어드리겠습니다! Java (0)	2022.09.19
[백준 P21610] 마법사 상어와 비바라기 Java (0)	2022.09.19
[백준 P17779] 게리멘더링 2 (0)	2022.09.06
[백준 P20056] 마법사 상어와 파이어볼 Java (0)	2022.09.06

'알고리즘' Related Articles

Comments