문제 설명
문제에 제시된 조건대로 블록그룹을 제거하다가 더 이상 제거 할 수 없게 되었을 때 그 때까지 획득한 점수의 합을 출력하는 문제이다.
문제 풀이
최대 점수 혹은 최소 점수를 구하는게 아니라 문제에 주어진 조건대로 시뮬레이션하면 되는 문제이다. 이 문제에서 요구하는 조건들이 살짝 까다로울 수 있으며 중력작용, 회전, 격자탐색 등을 조합해서 풀어야한다. 따라서 각 기능의 구현시 실수를 줄여야 문제 풀이에 애먹지 않는다.
위 그림에 가능한 모든 블록그룹들을 표시해 놓았다. 그 중에서 블록그룹에 속하는 블록의 개수가 2이상이 아닌 블록그룹은 문제 조건과 맞지 않는 블록그룹이 된다.
위와 같이 블록그룹을 식별하도록 구현하면 된다. 블록그룹의 조건을 정리하면 아래와 같다.
1. 일반 블록이 하나 이상 포함되어야 한다.
2. 검정색 블록은 포함되면 안된다.
3. 무지개 블록은 개수에 상관없이 포함할 수 있다.
4. 포함된 일반 블록의 번호는 모두 같아야 한다.
5. 블록그룹에 속하는 블록의 개수는 2이상이어야 한다.
=> 방문하지 않은 일반 블록을 만나면 그 블록에서 일반 블록 번호가 같거나 무지개 블록을 방문하는 사방탐색을 DFS or BFS로 구현하면 되겠다. 단, 이 때 블록의 개수가 2이상이어야 한다.
그 다음은 제거할 블록그룹을 선정해야 한다. 위에서 식별될 여러 블록그룹중에서 아래조건에 맞는 블록그룹을 선택하여 제거하자.
- 각 조건을 만족하는 블록그룹이 여러개라면 그 다음 조건을 적용한다.
- 크기가 가장 큰 블록그룹
- 무지개 블록을 가장 많이 포함하는 블록그룹
- 기준 블록의 행이 가장 큰 블록그룹
- 기준 블록의 열이 가장 큰 블록그룹
=> 블록그룹을 얻어 낼 때, 위의 정보들을 저장하고 있다가 다음 블록그룹과 비교해야 한다. (compareTo() overriding)
다음으로는 선택된 블록그룹을 제거한 뒤에 중력을 작용시키고, 반시계로 90도 회전 한 후에 다시 중력을 작용시켜야 한다.
- 중력 작용 시에 검은색 블록은 영향을 받지 않으며, 다른종류의 블록은 검은색 블록을 통과할 수 없다.
=> 투 포인터나 큐를 이용하여 중력을 작용시키되, 검은색 블록을 중간에 만나면 처리가 필요하다.
- 반시계로 90 회전시켜야 한다.
=> 회전 전후의 행과 열의 관계와 임시 배열을 이용하여 구현한다.
위 과정을 반복하면 된다.
import java.awt.Point;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static class Result implements Comparable<Result> {
int rainbowCnt;
int cnt;
int row;
int col;
public Result(int rainbowCnt, int cnt, int row, int col) {
super();
this.rainbowCnt = rainbowCnt;
this.cnt = cnt;
this.row = row;
this.col = col;
}
@Override
public int compareTo(Result o) {
return this.cnt != o.cnt ? o.cnt - this.cnt
: (this.rainbowCnt != o.rainbowCnt ? o.rainbowCnt - this.rainbowCnt
: (this.row != o.row ? o.row - this.row : o.col - this.col));
}
}
static int n, m, ans;
static int grid[][];
static boolean[][] visited;
static int[] dy = { 0, 1, 0, -1 };
static int[] dx = { 1, 0, -1, 0 };
public static void main(String[] args) throws Exception {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
grid = new int[n][n];
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
grid[i][j] = Integer.parseInt(st.nextToken());
}
}
while (removeLargestGroup()) {
fall();
rotate();
fall();
}
System.out.println(ans);
}
static void rotate() {
int[][] tmp = new int[n][n];
visited = new boolean[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
tmp[i][j] = grid[j][n - 1 - i];
}
}
grid = tmp;
}
static void fall() {
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
int lastBlack = n - 1;
for (int j = n - 1; j >= 0; j--) {
if (grid[j][i] >= 0) {
q.add(grid[j][i]);
grid[j][i] = -2;
} else if (grid[j][i] == -1) {
for (int k = lastBlack; k > j; k--) {
if (grid[k][i] == -2 && !q.isEmpty()) {
grid[k][i] = q.poll();
}
}
lastBlack = j;
}
}
for (int j = lastBlack; j >= 0; j--) {
if (grid[j][i] == -2 && !q.isEmpty()) {
grid[j][i] = q.poll();
}
}
}
}
static boolean removeLargestGroup() {
for (int k = 0; k < n; k++) {
Arrays.fill(visited[k], false);
}
Result largestGroup = null;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 일반블록을 적어도 하나 이상 포함
if (grid[i][j] > 0) {
Result tmp = bfs(i, j);
if (tmp != null) {
if (largestGroup == null) {
largestGroup = tmp;
} else {
if (largestGroup.compareTo(tmp) > 0) {
largestGroup = tmp;
}
}
}
for (int k = 0; k < n; k++) {
Arrays.fill(visited[k], false);
}
}
}
}
if (largestGroup == null) {
return false;
}
removeBfs(largestGroup.row, largestGroup.col);
return true;
}
static void removeBfs(int row, int col) {
Queue<Point> q = new ArrayDeque<>();
visited[row][col] = true;
q.add(new Point(col, row));
int cnt = 0;
int color = grid[row][col];
while (!q.isEmpty()) {
int curRow = q.peek().y;
int curCol = q.peek().x;
q.poll();
// 빈 공간 := -2
grid[curRow][curCol] = -2;
cnt++;
for (int i = 0; i < 4; i++) {
int nRow = curRow + dy[i];
int nCol = curCol + dx[i];
if (inRange(nRow, nCol) && !visited[nRow][nCol]
&& (grid[nRow][nCol] == 0 || grid[nRow][nCol] == color)) {
visited[nRow][nCol] = true;
q.add(new Point(nCol, nRow));
}
}
}
ans += cnt * cnt;
}
static Result bfs(int row, int col) {
Queue<Point> q = new ArrayDeque<>();
visited[row][col] = true;
q.add(new Point(col, row));
int color = grid[row][col];
int cnt = 0;
int rainbowCnt = 0;
int sRow = 100;
int sCol = 100;
while (!q.isEmpty()) {
int curRow = q.peek().y;
int curCol = q.peek().x;
q.poll();
cnt++;
if (grid[curRow][curCol] == 0) {
rainbowCnt++;
} else {
if (sRow > curRow) {
sRow = curRow;
sCol = curCol;
} else if (sRow == curRow && sCol > curCol) {
sCol = curCol;
}
}
for (int i = 0; i < 4; i++) {
int nRow = curRow + dy[i];
int nCol = curCol + dx[i];
if (inRange(nRow, nCol) && !visited[nRow][nCol]
&& (grid[nRow][nCol] == 0 || grid[nRow][nCol] == color)) {
visited[nRow][nCol] = true;
q.add(new Point(nCol, nRow));
}
}
}
if (cnt < 2) {
return null;
}
return new Result(rainbowCnt, cnt, sRow, sCol);
}
static boolean inRange(int row, int col) {
return 0 <= row && row < n && 0 <= col && col < n;
}
}