[알고리즘][X] 색깔 폭탄
2024. 3. 25. 23:04ㆍ알고리즘 풀이/Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
static class Bomb {
int x;
int y;
int color;
public Bomb(int x, int y, int color) {
this.x = x;
this.y = y;
this.color = color;
}
@Override
public String toString() {
return "Bomb{" +
"x=" + x +
", y=" + y +
", color=" + color +
'}';
}
}
static class Bombc {
int x;
int y;
int redSize;
List<Bomb> bombs;
public Bombc() {
this.x = -1;
this.y = -1;
this.redSize = 0;
this.bombs = new ArrayList<>();
}
@Override
public String toString() {
return "Bombc{" +
"x=" + x +
", y=" + y +
", redSize=" + redSize +
", bombs=" + bombs +
'}';
}
}
static int n;
static int m;
static int[][] map;
static boolean[][] visited;
static PriorityQueue<Bombc> bombs;
static int result;
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());
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());
}
}
result = 0;
while(true){
Bombc bomb = findBomb();
// System.out.println(bomb);
if (bomb == null) {
break;
}
bomb(bomb);
gravity();
rotate();
gravity();
}
// System.out.println(bombs);
// bomb();
// rotate();
// gravity();
// print();
// rotate();
// print();
// gravity();
// print();
System.out.println(result);
}
private static void print() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(map[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
private static void rotate() {
int[][] rotateMap = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
rotateMap[n - 1 - j][i] = map[i][j];
}
}
map = rotateMap;
}
private static void gravity() {
for (int j = 0; j < n; j++) {
for (int i = n - 1; i >= 0; i--) {
if (map[i][j] < 0) {
continue;
}
for (int k = i + 1; k <= n; k++) {
if (k == n) {
if (k - 1 == i) {
break;
}
map[n - 1][j] = map[i][j];
map[i][j] = -2;
break;
}
// 빈 공간이 아니라면
if (map[k][j] != -2) {
if (k - 1 == i) {
break;
}
map[k - 1][j] = map[i][j];
map[i][j] = -2;
break;
}
}
}
}
}
private static void bomb(Bombc bomb) {
for (Bomb bomb1 : bomb.bombs) {
map[bomb1.x][bomb1.y] = -2;
}
result += bomb.bombs.size() * bomb.bombs.size();
}
private static Bombc findBomb() {
visited = new boolean[n][n];
bombs = new PriorityQueue<>(new Comparator<Bombc>() {
@Override
public int compare(Bombc o1, Bombc o2) {
// 문제의 조건에 따르면 우선순위를 매기는 방식이 아래와 같이 더 있었는데 고려 안해줌
if (o1.bombs.size() == o2.bombs.size()){
if (o1.redSize == o2.redSize) {
if (o1.x == o2.x) {
return o1.y - o2.y;
}
return o2.x - o1.x;
}
return o1.redSize - o2.redSize;
}
return o2.bombs.size() - o1.bombs.size();
}
});
List<int[]> reds = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 0) {
reds.add(new int[]{i, j});
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 빨간색이라도 넘어감
if (visited[i][j] || map[i][j] <= 0) {
continue;
}
// TreeSet<Bomb> bomb = new TreeSet<>(new Comparator<Bomb>() {
// @Override
// public int compare(Bomb o1, Bomb o2) {
// if (o1.x == o2.x) {
// return o1.y - o2.y;
// } else {
// return o2.x - o1.x;
// }
// }
// });
Bombc bombc = new Bombc();
dfs(i, j, map[i][j], bombc);
for (int[] red : reds) {
int x = red[0];
int y = red[1];
visited[x][y] = false;
}
if (bombc.bombs.size() <= 1) {
continue;
}
bombs.add(bombc);
}
}
return bombs.poll();
}
private static void dfs(int x, int y, int color, Bombc bombc) {
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (0 <= nx && nx < n && 0 <= ny && ny < n && !visited[nx][ny] && (map[nx][ny] == color || map[nx][ny] == 0)) {
visited[nx][ny] = true;
if (map[nx][ny] == color) {
if (nx == bombc.x) {
if (ny < bombc.y) {
bombc.y = ny;
}
} else {
if (nx > bombc.x) {
bombc.x = nx;
bombc.y = ny; // 이거 고려 안해줬음
}
}
bombc.bombs.add(new Bomb(nx, ny, color));
} else { //빨간색이면 x, y 갱신 안함
bombc.redSize++;
bombc.bombs.add(new Bomb(nx, ny, 0));
}
dfs(nx, ny, color, bombc);
}
}
}
}
나의 풀이
- 맞다고 생각하면 밀고 가야 한다. 그걸 구현으로 극복해야 한다고 생각한다.
- nx > bombc.x일 때 bombc.y는 ny와 다를 수 있어서 같게 만들어줘야 하는데 이걸 놓쳤다.
- 우선순위 조건을 모두 고려하지 않아 틀렸다.
- 그러나 구현은 잘되었다
'알고리즘 풀이 > Java' 카테고리의 다른 글
[알고리즘][X] 녹색 옷 입은 애가 젤다지? (0) | 2024.03.27 |
---|---|
[알고리즘][X] 왕실의 기사 대결 (0) | 2024.03.26 |
[알고리즘][X] 나무 타이쿤 (0) | 2024.03.25 |
[알고리즘] 코드트리 오카마세 (0) | 2024.03.25 |
[알고리즘] 루돌프의 반란 (0) | 2024.03.24 |