[백준] 21609. 상어 중학교 (Java, 자바)

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

21609번: 상어 중학교

 

 

문제

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

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

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

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

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

다음은 N = 5, M = 3인 경우의 예시이다.

여기서 찾을 수 있는 크기가 가장 큰 블록 그룹을 다음과 같이 빨간색으로 표시했다.

블록 그룹이 제거되면 다음과 같이 변하고, 점수 8^2점을 획득한다.

중력이 작용하면 다음과 같이 변한다.

90도 반시계방향으로 회전한 결과는 다음과 같다.

다시 여기서 중력이 작용하면 다음과 같이 변한다.

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

---

 

 

입력

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

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

---

 

 

출력

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

---

 

 

제한

• 1 ≤ N ≤ 20
• 1 ≤ M ≤ 5

---

 

 

🚀풀이

BFS or DFS 탐색 + 구현력이 필요한 문제!

삼성 기출답게 굉장히 문제가 길고 조건도 많다.

구현할 때는 문제에서 주어진대로 1번부터 5번까지 순서대로 함수로 분리하여 구현을 했다.

블록 그룹을 찾을 때는 BFS 탐색을 사용했고, 블록 그룹의 정보를 저장하기 위해

Block 클래스를 만들어 블록 그룹의 기준 블록 x y 좌표,  블록의 색상, 블록 그룹의 총 블록 수, 블록 그룹에 속한 무지개 블록 수를 저장했다. 

이렇게 Block 클래스를 만들어 두었더니 가장 큰 블록을 찾는 조건을 간단하게 처리할 수 있었다.

BFS 탐색을 할 때 중요한 점은 무지개 블록의 방문처리를 탐색할 때마다 초기화해야 한다는 점이다.

각 기능마다 함수로 분리하여 구현을 하여 코드의 가독성을 챙겼다.

또 가독성을 챙기기 위해 최대한 중첩 if문을 사용하지 않고, continue 문을 사용하여 조건을 처리했다.

삼성 기출에서 자주 나오는 배열 돌리기, 중력 작용 등은 꼭 혼자 힘으로 구현해보는 것을 추천한다.

---

 

 

코드

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

public class Main {
	// 검정 블록, 무지개 블록, 빈 칸
	static int BLACK = -1, RAINBOW = 99, EMPTY = 0;
	static int N, M, sum;	// 격자 크기, 색상 개수, 점수 합
	static int[][] map;	// 격자
	static int[] dx = { -1, 0, 1, 0 }, dy = { 0, 1, 0, -1 };	// 상 우 하 좌
	static boolean[][] visited;	// 방문 배열

	public static void main(String[] args) throws Exception {
		init(); // 입력

		solution(); // 풀이

		printResult(); // 결과 출력
	}

	static void solution() {
		while (true) {
			// 1. 크기가 가장 큰 블록 크룹을 찾는다.
			Block standardBlock = findMaxBlockGroupe();
			// 더 이상 블록 그룹이 없는 경우
			if (standardBlock == null) {
				return;
			}

			// 점수 합산
			sum += standardBlock.sum * standardBlock.sum;

			// 2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다.
			removeBlock(standardBlock);

			// 3. 격자에 중력이 작용한다.
			applyGravity();

			// 4. 격자가 90도 반시계 방향으로 회전한다.
			rotateMap();

			// 5. 다시 격자에 중력이 작용한다.
			applyGravity();
		}
	}

	static Block findMaxBlockGroupe() {
		visited = new boolean[N][N];
		Block maxBlock = new Block(0, 0, EMPTY, Integer.MIN_VALUE, Integer.MIN_VALUE);

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				// 검정 블록이면 skip
				if (map[i][j] == BLACK) {
					continue;
				}
				// 무지개 블록이면 skip
				if (map[i][j] == RAINBOW) {
					continue;
				}
				// 비어있으면 skip
				if (map[i][j] == EMPTY) {
					continue;
				}
				// 이미 방문했으면 skip
				if (visited[i][j]) {
					continue;
				}

				// bfs 탐색 전에 무지개 블록만 방문 처리 초기화
				initRainBowVisited();
				
				Block cur = bfsBlock(i, j, map[i][j]);

				// 그룹 블록 수 2개보다 작으면 skip
				if (cur == null) {
					continue;
				}
				// 최대 블록 수 갱신
				if (maxBlock.compareBlock(cur)) {
					maxBlock = cur;
				}
			}
		}

		// 초기값 그대로라면 블록그룹 못찾았으므로 null return
		if (maxBlock.color == EMPTY) {
			return null;
		}
		return maxBlock;
	}

	// 무지개 블록만 방문 처리 초기화 -> 다른 색깔의 블록에서도 무지개 블록은 방문할 수 있으므로
	static void initRainBowVisited() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == RAINBOW) {
					visited[i][j] = false;
				}
			}
		}
	}

	// x, y 좌표부터 같은 color 블록 bfs 탐색
	static Block bfsBlock(int x, int y, int color) {
		Queue<Integer> qx = new LinkedList<>();
		Queue<Integer> qy = new LinkedList<>();
		qx.offer(x);
		qy.offer(y);
		visited[x][y] = true;
		int sum = 1;
		int rainbowSum = 0;

		while (!qx.isEmpty()) {
			int cx = qx.poll();
			int cy = qy.poll();

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

				// 범위 나가면 skip
				if (outOfRange(nx, ny)) {
					continue;
				}
				// 검정 블록이면 skip
				if (map[nx][ny] == BLACK) {
					continue;
				}
				// 비어있으면 skip
				if (map[nx][ny] == EMPTY) {
					continue;
				}
				// 이미 방문했으면 skip
				if (visited[nx][ny]) {
					continue;
				}
				// color 다를때 무지개 블록일때만 넣기
				if (map[nx][ny] != color) {
					if (map[nx][ny] == RAINBOW) {
						rainbowSum++;
						sum++;
						visited[nx][ny] = true;
						qx.offer(nx);
						qy.offer(ny);
					}
					continue;
				}

				sum++;
				visited[nx][ny] = true;
				qx.offer(nx);
				qy.offer(ny);
			}
		}

		// 그룹에 속한 블록의 개수가 2보다 작으면 null 리턴
		if (sum < 2) {
			return null;
		} else {
			return new Block(x, y, color, sum, rainbowSum);
		}
	}

	// 범위 체크
	static boolean outOfRange(int x, int y) {
		return x < 0 || x >= N || y < 0 || y >= N;
	}

	// 기준 블럭과 같은 그룹 모두 제거
	static void removeBlock(Block block) {
		Queue<Integer> qx = new LinkedList<>();
		Queue<Integer> qy = new LinkedList<>();
		visited = new boolean[N][N];
		qx.offer(block.x);
		qy.offer(block.y);
		visited[block.x][block.y] = true;
		map[block.x][block.y] = EMPTY;

		while (!qx.isEmpty()) {
			int cx = qx.poll();
			int cy = qy.poll();
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				// 범위 나가면 skip
				if (outOfRange(nx, ny)) {
					continue;
				}
				// 검정 블록이면 skip
				if (map[nx][ny] == BLACK) {
					continue;
				}
				// 비어있으면 skip
				if (map[nx][ny] == EMPTY) {
					continue;
				}
				// 이미 방문했으면 skip
				if (visited[nx][ny]) {
					continue;
				}
				// color 다를때 무지개 블록일때만 넣기
				if (map[nx][ny] != block.color) {
					if (map[nx][ny] == RAINBOW) {
						map[nx][ny] = EMPTY;
						visited[nx][ny] = true;
						qx.offer(nx);
						qy.offer(ny);
					}
					continue;
				}

				map[nx][ny] = EMPTY;
				visited[nx][ny] = true;
				qx.offer(nx);
				qy.offer(ny);
			}
		}
	}

	// 중력 작용
	static void applyGravity() {
		for (int i = 0; i < N; i++) {
			for (int j = N - 2; j >= 0; j--) {
				if (map[j][i] == BLACK) {
					continue;
				}
				if (map[j][i] == EMPTY) {
					continue;
				}
				moveBlock(j, i);
			}
		}
	}

	// 블록 한개씩 옮기기
	static void moveBlock(int x, int y) {
		int cx = x;
		while (true) {
			cx++;
			// 범위 벗어나면 break
			if (cx >= N) {
				break;
			}
			// 검정 블록이면 break;
			if (map[cx][y] == BLACK) {
				break;
			}
			// 빈 칸 아니면 break;
			if (map[cx][y] != EMPTY) {
				break;
			}
		}
		cx--;

		// 안움직였으면 return
		if (cx == x) {
			return;
		}

		map[cx][y] = map[x][y];
		map[x][y] = EMPTY;
	}

	// 90도 반시계 방향으로 격자 회전
	static void rotateMap() {
		int[][] map_copy = new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map_copy[i][j] = map[j][N - i - 1];
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				map[i][j] = map_copy[i][j];
			}
		}
	}

	// 결과 출력
	static void printResult() {
		System.out.println(sum);
	}

	// 입력
	static void init() 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());
		sum = 0;
		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] == -1) {
					map[i][j] = BLACK;
				} else if (map[i][j] == 0) {
					map[i][j] = RAINBOW;
				}
			}
		}
	}

	// 블록 클래스
	static class Block {
		// 기준 블록의 x y 좌표, 색상, 블록그룹의 총 블록 수, 블록그룹에 속한 무지개 블록 수
		int x, y, color, sum, rainbowSum;

		public Block(int x, int y, int color, int sum, int rainbowSum) {
			this.x = x;
			this.y = y;
			this.color = color;
			this.sum = sum;
			this.rainbowSum = rainbowSum;
		}

		public boolean compareBlock(Block other) {
			// 나보다 other이 max이면 true

			// 블록 수로 비교
			if (this.sum != other.sum)
				return this.sum < other.sum;

			// 무지개 블록 수로 비교
			if (this.rainbowSum != other.rainbowSum)
				return this.rainbowSum < other.rainbowSum;

			// 행으로 비교
			if (this.x != other.x)
				return this.x < other.x;

			// 행으로 비교
			return this.y < other.y;
		}
	}
}

 

 

 

결과