백준 21609번 상어중학교(자바) - 구현, bfs / 삼성 sw 역량 기출
문제
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 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인 경우의 예시이다.
| 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 |
여기서 찾을 수 있는 크기가 가장 큰 블록 그룹을 다음과 같이 빨간색으로 표시했다.
| 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 |
블록 그룹이 제거되면 다음과 같이 변하고, 점수 82점을 획득한다.
| 2 | 2 | -1 | 3 | 1 |
| 2 | 0 | -1 | ||
| 1 | 2 | |||
| -1 | 1 | 3 | 2 | |
| 2 | 2 | 1 |
중력이 작용하면 다음과 같이 변한다.
| -1 | 3 | 1 | ||
| 0 | -1 | |||
| 2 | 2 | 1 | 2 | |
| -1 | 1 | 3 | 2 | |
| 2 | 2 | 2 | 1 |
90도 반시계방향으로 회전한 결과는 다음과 같다.
| 1 | -1 | 2 | 2 | 1 |
| 3 | 0 | 1 | 3 | 2 |
| -1 | 2 | 1 | 2 | |
| 2 | ||||
| 2 | -1 |
다시 여기서 중력이 작용하면 다음과 같이 변한다.
| 1 | -1 | |||
| 3 | 2 | 2 | 1 | |
| -1 | 1 | 3 | 2 | |
| 2 | 1 | 2 | ||
| 0 | 2 | -1 | 2 |
오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.
입력
첫째 줄에 격자 한 변의 크기 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주의!! 무지개 블록은 bfs에서 visited 방문체크를 조심해야 한다.
무지개 블록은 여러 그룹에 동시에 속하는게 가능하다!
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static class Group implements Comparable<Group> {
int x;
int y;
int rainbowCnt;
int totalCnt;
Group (int x, int y, int rainbowCnt, int totalCnt) {
this.x = x;
this.y = y;
this.rainbowCnt = rainbowCnt;
this.totalCnt = totalCnt;
}
@Override
public int compareTo(Group group) {
if (this.totalCnt == group.totalCnt) {
if (this.rainbowCnt == group.rainbowCnt) {
if (this.x == group.x) {
return group.y - this.y;
}
return group.x - this.x;
}
return group.rainbowCnt - this.rainbowCnt;
}
return group.totalCnt - this.totalCnt;
}
}
static int n;
static boolean visited[][];
static int[][] map;
static int[] dx = {-1,1,0,0};
static int[] dy = {0,0,-1,1};
static List<Group> list;
static int answer = 0;
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());
int 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) {
if (!findGroup()) break;
gravity();
rotation();
gravity();
}
System.out.println(answer);
}
static boolean findGroup() {
list = new ArrayList<>();
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j] && map[i][j] > 0) {
bfs(i, j, true);
}
}
}
visited = new boolean[n][n];
if (list.isEmpty()) return false;
else {
Collections.sort(list);
bfs(list.get(0).x, list.get(0).y, false);
removeBlock();
}
return true;
}
static void removeBlock() {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] == true) {
count++;
map[i][j] = -2;
}
}
}
answer += (int)Math.pow(count, 2);
}
static void bfs(int x, int y, boolean flag) {
int rainbow = 0;
int total = 1;
visited[x][y] = true;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
while (!queue.isEmpty()) {
int[] now = queue.poll();
for (int i = 0; i < 4; i++) {
int nx = now[0] + dx[i];
int ny = now[1] + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) continue;
if (map[nx][ny] == map[x][y] || map[nx][ny] == 0) {
visited[nx][ny] = true;
queue.offer(new int[]{nx, ny});
if (map[nx][ny] == 0) rainbow++;
total+=1;
}
}
}
if (total >= 2) list.add(new Group(x, y, rainbow, total));
if (flag) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 0) visited[i][j] = false;
}
}
}
}
public static void gravity() {
for (int i = n-1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (map[i][j] >= 0) {
int nx = i;
while (true) {
nx += 1;
if (nx >= n || map[nx][j] != -2) break;
}
nx--;
if (nx != i) {
map[nx][j] = map[i][j];
map[i][j] = -2;
}
}
}
}
}
public static void rotation() {
int[][] tmp = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
tmp[n-j-1][i] = map[i][j];
}
}
map = tmp;
}
}