👀 문제 설명
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다.
블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다. 블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.
오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.
- 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
- 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
- 격자에 중력이 작용한다.
- 격자가 90도 반시계 방향으로 회전한다.
- 다시 격자에 중력이 작용한다.
격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.
다음은 N = 5, M = 3인 경우의 예시이다.
여기서 찾을 수 있는 크기가 가장 큰 블록 그룹을 다음과 같이 빨간색으로 표시했다.
블록 그룹이 제거되면 다음과 같이 변하고, 점수 82점을 획득한다.
중력이 작용하면 다음과 같이 변한다.
90도 반시계방향으로 회전한 결과는 다음과 같다.
다시 여기서 중력이 작용하면 다음과 같이 변한다.
오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.
입력
첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.
둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.
출력
첫째 줄에 획득한 점수의 합을 출력한다.
제한
- 1 ≤ N ≤ 20
- 1 ≤ M ≤ 5
예제 입력 1
5 3
2 2 -1 3 1
3 3 2 0 -1
0 0 0 1 2
-1 3 1 3 2
0 3 2 2 1
예제 출력 1
77
예제 입력 2
6 4
2 3 1 0 -1 2
2 -1 4 1 3 3
3 0 4 2 2 1
-1 4 -1 2 3 4
3 -1 4 2 0 3
1 2 2 2 2 1
예제 출력 2
125
예제 입력 3
4 3
1 1 1 3
3 2 3 3
1 2 -1 3
-1 -1 1 1
예제 출력 3
33
✍🏻풀이
블록 그룹의 정보를 갖는 클래스 BlockGroup을 만들고, ArrayList<BlockGroup>을 사용해 가장 큰 블록 그룹을 찾는다.
블록 그룹을 구할 때는 BFS로 무지개 블록이거나, 색이 동일할 때 queue에 넣는 방식으로 구했다.
-> ArrayList<BlockGroup>이 sort 될 때는 문제에 제시된 조건으로 정렬하기 위해 BlockGroup은 Comparator를 구현한다.
1. 크기가 가장 큰 블록을 찾는 메소드 findBigBlock()
2. 1에서 찾은 블록 그룹의 모든 블록을 제거하고, 점수를 획득하는 메소드 removeBlocks()
3 & 5. 격자에 중력이 작용하는 메소드 gravity()
4. 격자가 90도 반시계 방향으로 회전하는 메소드 rotateCCW90()
을 사용해 구현해줬다.
나는 removeBlocks()에서 무지개 블록들의 방문 표시를 체크 해제 하기 위해 rainbowBlocks 라는 리스트에 무지개 블록의 위치를 담아두는데, 이 rainbowBlocks는 1~5가 반복된 후에 매번 다시 업데이트 시켜줘야 한다!!!!
=> 이것때문에 테스트케이스는 다 맞는데 계속 제출하자마자 틀렸다고 떴다..! 조심하기...
코드
package boj;
// 상어 중학교 (https://www.acmicpc.net/problem/21609 )
import java.util.*;
import java.io.*;
public class BOJ_21609 {
private static class BlockGroup implements Comparable<BlockGroup> {
private int size; // 사이즈
private int[] standard; // 기준 블록의 행과 열
private int rainbowNum; // 무지개 블록의 수
private BlockGroup(int size, int[] standard, int rainbowNum) {
this.size = size;
this.standard = standard;
this.rainbowNum = rainbowNum;
}
@Override
public int compareTo(BlockGroup o) {
if (this.size != o.size) { // 크기 내림차순 정렬
return o.size - this.size;
} else {
if (this.rainbowNum != o.rainbowNum) { // 무지개 블록 수 내림차순 정렬
return o.rainbowNum - this.rainbowNum;
} else {
if (this.standard[0] != o.standard[0]) { // 행 내림차순 정렬
return o.standard[0] - this.standard[0];
} else { // 열 내림차순 정렬
return o.standard[1] - this.standard[1];
}
}
}
}
}
private static int N, M;
private static int[][] map;
private static boolean[][] visitedGroups;
private static int[] dx = { 1, 0, -1, 0 };
private static int[] dy = { 0, 1, 0, -1 };
private static ArrayList<int[]> rainbowBlocks = new ArrayList<>();
private static Queue<int[]> queue = new LinkedList<>();
private static BlockGroup delete;
private static int ans = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// input
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) rainbowBlocks.add(new int[] { i, j });
}
}
while (true) {
visitedGroups = new boolean[N][N];
if (!findBigBlock())break;
removeBlocks();
gravity();
rotateCCW90();
gravity();
addRainbowBlocks();
}
bw.write(ans + "\n");
bw.flush();
bw.close();
}
// 1. 크기가 가장 큰 블록을 찾는다.
// 1-1. 그런 블록 그룹이 여러 개라면, 포함된 무지개 블록의 수가 가장 많은 블록 그룹
// 1-2. 그런 블록도 여러개라면, 기존 블록의 행이 가장 큰 것을, 그것도 여러개이면 열이 가장 큰 것
private static boolean findBigBlock() {
ArrayList<BlockGroup> groups = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
// map[i][j]가 일반 블록이고, 아직 방문하지 않은 곳이라면
if (map[i][j] > 0 && !visitedGroups[i][j]) { // map[i][j]가 포함되는 블록 그룹을 구한다.
visitedGroups[i][j] = true;
queue.offer(new int[] { i, j });
int groupSize = 1;
int rainbowNum = 0;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int dir = 0; dir < 4; dir++) {
int adjX = cur[0] + dx[dir];
int adjY = cur[1] + dy[dir];
if (!validatePos(adjX, adjY)) continue;
if (!visitedGroups[adjX][adjY] && (map[adjX][adjY] == 0 || map[adjX][adjY] == map[i][j])) {
if (map[adjX][adjY] == 0) rainbowNum++;
visitedGroups[adjX][adjY] = true;
queue.offer(new int[] { adjX, adjY });
groupSize++;
}
}
}
// 블록 그룹이 가능한 경우 (블록의 개수가 2보다 크거나 같아야 함)
if (groupSize > 1) {
groups.add(new BlockGroup(groupSize, new int[] { i, j }, rainbowNum));
}
// (블록 그룹을 구했다면, 무지개 블록들의 visited는 false로 바꾼다.
for (int[] rainbow : rainbowBlocks) {
visitedGroups[rainbow[0]][rainbow[1]] = false;
}
}
}
}
if (groups.size() == 0) return false;
Collections.sort(groups);
delete = groups.get(0);
return true;
}
// 2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. & 점수 획득
private static void removeBlocks() {
int[] standard = delete.standard;
boolean[][] visited = new boolean[N][N];
visited[standard[0]][standard[1]] = true;
queue.offer(new int[] { standard[0], standard[1] });
while (!queue.isEmpty()) {
int[] cur = queue.poll();
for (int dir = 0; dir < 4; dir++) {
int adjX = cur[0] + dx[dir];
int adjY = cur[1] + dy[dir];
if (!validatePos(adjX, adjY)) continue;
if (!visited[adjX][adjY] && (map[adjX][adjY] == 0 || map[adjX][adjY] == map[standard[0]][standard[1]])) {
map[adjX][adjY] = -2; // 블록을 제거한다.
visited[adjX][adjY] = true;
queue.offer(new int[] { adjX, adjY });
}
}
}
map[standard[0]][standard[1]] = -2;
ans += delete.size * delete.size;
}
// 3 & 5. 격자에 중력이 작용한다.
private static void gravity() {
if (N == 1) return;
for (int j = 0; j < N; j++) {
int cnt = 0;
for (int i = 0 ; i < N; i++) {
if (map[i][j] >= -1) cnt++;
}
if (cnt == N) continue; // j열에는 꽉 차있으므로 중력이 작용해도 블록이 아래로 내려오지 않는다.
// 블록을 아래로
for (int i = 1; i < N; i++) {
if (map[i][j] == -2) {
for (int up = i - 1; up >= 0; up--) {
if (map[up][j] == -1) break;
map[up + 1][j] = map[up][j];
map[up][j] = -2;
}
}
}
}
}
// 4. 격자가 90도 반시계 방향으로 회전
private static void rotateCCW90() {
int[][] newMap = new int[N][N];
for (int j = N - 1; j >= 0; j--) {
for (int i = 0; i < N; i++) {
newMap[N - 1 - j][i] = map[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
map[i][j] = newMap[i][j];
}
}
}
// + 무지개 블록 위치 업데이트
private static void addRainbowBlocks() {
rainbowBlocks.clear();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 0) rainbowBlocks.add(new int[] { i, j });
}
}
}
private static boolean validatePos(int x, int y) {
if (x < 0 || x >= N || y < 0 || y >= N) return false;
return true;
}
}'숨막히는 알고말고 > 문제 풀이' 카테고리의 다른 글
| [Baekjoon] 마법사 상어와 토네이도 (0) | 2021.10.23 |
|---|---|
| [Baekjoon] 상어 초등학교 (0) | 2021.10.21 |
| [Baekjoon] 어른 상어 (0) | 2021.10.20 |
| [Baekjoon] 청소년 상어 (0) | 2021.10.19 |
| [Baekjoon] 마법사 상어와 파이어스톰 (0) | 2021.10.18 |
