[알고리즘][X] 색깔 폭탄

https://www.codetree.ai/training-field/frequent-problems/problems/colored-bomb/submissions?page=2&pageSize=20

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

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와 다를 수 있어서 같게 만들어줘야 하는데 이걸 놓쳤다.

- 우선순위 조건을 모두 고려하지 않아 틀렸다.

- 그러나 구현은 잘되었다