상어 중학교 질문!

[yukyeongmin]

https://www.acmicpc.net/problem/21609
약간 복잡한 구현 문제인데 문제에서 시키는 대로 분리해서 코드 짰습니다.
첫번째, 세번째 테케는 통과하는데 두번째 테스트케이스에서 다른 결과가 나옵니다.
어디가 문제인지 함께 고민해주실분을 찾습니다..!

https://github.com/sds-2021-summer-algorithm/java/tree/main/solution/BOJ_21609_%EC%83%81%EC%96%B4%EC%A4%91%ED%95%99%EA%B5%90

public class Main {
    static int N; // 판의 폭
    static int M; // 색의 종류

    static int[][] board;
    static int answer = 0 ;
    static final int None = 10;

    public static void main(String[] args) throws IOException{
        System.setIn(new FileInputStream("P21609/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new int[N][N];

        for(int i = 0 ; i<N ; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0 ; j<N; j++){ 
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        boolean flag = true;
        while(flag){
            flag = choose();
        }

        System.out.println(answer);
        br.close();
    }

    // 현재 보드상황에서 최적의 선택을 해야함.
    // 블록의 개수는 2개 이상
    // 일반 블록이 적어도 하나
    // 기준 블록은 무지개 블록이 아닌 블록 중에서 행, 열의 크기가 작은 블록
    public static boolean choose(){ // O(N^2)
        class position implements Comparable<position>{
            int x, y;
            int color;
            int totalBlock;
            int rainbow;

            public position(int x, int y, int color, int block, int rainbow) {
                this.x = x;
                this.y = y;
                this.color = color;
                this.totalBlock = block;
                this.rainbow = rainbow;
            }

            @Override
            public int compareTo(position o) {
                if(this.totalBlock == o.totalBlock){
                    if(this.rainbow == o.rainbow){
                        if(this.x == o.x){
                            return this.y - o.y;
                        }return this.x - o.x; // 오름차순
                    }return o.rainbow - this.rainbow;
                }return o.totalBlock - this.totalBlock; // 내림차순
            }

            @Override
            public String toString() {
                return "position [block=" + totalBlock + ", color=" + color + ", x=" + x + ", y=" + y + "]";
            }
        }

        PriorityQueue<position> pq = new PriorityQueue<position>();
        for(int i = 0 ; i<N ; i++){
            for(int j = 0 ; j<N; j++){ 
                // i,j를 기준블록으로 했을때 같은 색의 블록 수를 계산하자
                if(board[i][j]==-1 || board[i][j]==0 || board[i][j] == None) continue; 
                int color = board[i][j]; // 기준색

                int []block = count(i, j, color);
                if(block[0] < 2) continue;
                pq.offer( new position(i, j, color, block[0], block[1]) );
            }
        }

        if(pq.isEmpty()) return false;


        position top = pq.poll();
        int tx = top.x;
        int ty = top.y;
        answer += Math.pow(top.totalBlock, 2);

        delete(tx, ty, top.color);
        pq.clear();
        return true;
    }

    // x,y를 기준으로 삭제가능한 블록수 세기
    // return {전체 블록수, 무지개 블록수}
    public static int[] count(int x, int y, int color){
        int [] block = {0,0};
        boolean [][] check = new boolean[N][N];
        Queue<int[]> q = new LinkedList<int []>(); // 위치
        int []mx = {-1, 1, 0, 0};
        int []my = {0, 0, -1, 1};

        int [] start = {x,y}; 
        block[0] ++;
        if(board[x][y]==0) block[1]++;
        q.offer(start);
        check[x][y] = true; 

        while(!q.isEmpty()){
            int [] current = q.poll();
            for(int m = 0 ; m <4 ; m++){ // 상, 하, 좌, 우
                int nextX= current[0] + mx[m];
                int nextY = current[1] + my[m];
                int [] next = {nextX, nextY};
                if(nextX>=0 && nextX<N && nextY>=0 && nextY<N){
                    if( !check[nextX][nextY] ){
                        if(board[nextX][nextY]== color){
                            block[0]++;
                            q.offer(next);
                            check[nextX][nextY] = true; 
                        }else if(board[nextX][nextY] == 0 ){
                            block[1]++;
                            block[0]++;
                            q.offer(next);
                            check[nextX][nextY] = true; 
                        }
                    } 
                }
            }
        }
        return block;
    }

    // 기분블록, 제거할 색
    // 제거되는 블록의 개수를 세어 점수계산도 필요함.
    public static void delete(int x, int y, int color){
        boolean [][] check = new boolean[N][N];
        Queue<int[]> q = new LinkedList<int []>();
        int []mx = {-1, 1, 0, 0};
        int []my = {0, 0, -1, 1};

        int [] start = {x,y}; 
        q.offer(start);
        board[x][y] = None; // 삭제
        check[x][y] = true;

        while(!q.isEmpty()){
            int [] current = q.poll();
            for(int m = 0 ; m <4 ; m++){ // 상, 하, 좌, 우
                int nextX= current[0] + mx[m];
                int nextY = current[1] + my[m];
                int [] next = {nextX, nextY};
                if(nextX>=0 && nextX<N && nextY>=0 && nextY<N){
                    if(board[nextX][nextY]== color || board[nextX][nextY] == 0){
                        if( !check[nextX][nextY] ){
                            q.offer(next);
                            board[nextX][nextY] = None; // 삭제
                        }
                    } 
                }
            }
        }
        gravity();
        rotate();
        gravity();
    }

    public static void gravity(){ // O(N^2)
        for(int i = N-2 ; i >=0 ; i--){
            for(int j = N-1; j>=0 ; j--){
                int x = i; // 위아래
                if(board[i][j]==-1) continue; // 검은 블록
                if(board[i][j]==None) continue; // 빈칸

                while(board[x+1][j]==None){ // 아래쪽이 비어있으면
                    board[x+1][j] = board[x][j];
                    board[x][j] = None;
                    x ++;
                    if(x==N-1) break;
                }
            }
        }
    }

    // counter-clock wise
    public static void rotate(){ // O(2N^2)
        int[][] temp = new int[N][N];
        for(int i = 0 ; i<N ; i++){
            for(int j = 0 ; j<N; j++){ 
                temp[i][j]=board[i][j]; // copy
            }
        }

        for(int i = 0 ; i<N ; i++){
            for(int j = 0 ; j<N; j++){ 
                board[i][j] = temp[j][N-i-1];
            }
        }
    }
}
`

[wjdgns7712]

중력이 작용되는 부분이 블록전체가 다 내려오는것도 아니고 사라진 부분에 한해서만 내려오는게 어렵네요... 문제를 조금 더 고민해보겠습니다!

[wjdgns7712]

혹시 계속 129 나오시나요..??

[wjdgns7712]

제가 제대로 코드를 읽은게 맞는지 모르겠지만, 제가 이해한바로는..

우선,

@Override
public int compareTo(position o) {
    if(this.totalBlock == o.totalBlock){
        if(this.rainbow == o.rainbow){
            if(this.x == o.x){
                return this.y - o.y;
            }return this.x - o.x; // 오름차순
        }return o.rainbow - this.rainbow;
    }return o.totalBlock - this.totalBlock; // 내림차순
}

이 부분에서 x, y값도 오름차순이 아닌 내림차순으로 처리해주셔야할거같아요.

그리고...

// i,j를 기준블록으로 했을때 같은 색의 블록 수를 계산하자
if(board[i][j]==-1 || board[i][j]==0 || board[i][j] == None) continue; 
int color = board[i][j]; // 기준색

위의 조건에서 걸어주셨다시피,

i, j값이 0부터 N-1까지 돌면서 위의 조건을 만족해서 다음 프로세스로 넘어간다면, 무조건 위의 compare 함수에서의 x, y값조건은 항상 충족하게 됩니다. 그래서 compare 함수도 줄일수있을것 같아요.

상어초등학교 문제와 마찬가지로... PQ는 좋은선택은 아닌것으로 생각됩니다! 블록에 포함되는 총 갯수, 무지개색 갯수 이 두가지만 비교해줘도 충분히 해결이 되므로 PQ를 사용안하는쪽으로 해보시는걸 권장해드립니다!

마지막으로,

// counter-clock wise
public static void rotate(){ // O(2N^2)
    int[][] temp = new int[N][N];
    for(int i = 0 ; i<N ; i++){
        for(int j = 0 ; j<N; j++){ 
            temp[i][j]=board[i][j]; // copy
        }
    }

    for(int i = 0 ; i<N ; i++){
        for(int j = 0 ; j<N; j++){ 
            board[i][j] = temp[j][N-i-1];
        }
    }
}

위 함수에서, temp 변수를 선언과 동시에 초기화를 해줬으므로 굳이 copy하는 과정은 없어도 될것같습니다!

코드스타일이 많이 달라서 제가 잘 이해한게 맞는건지 모르겠네요.. 도움이 될지모르겠지만 우선 제 코드는 아래 남겨놓겠습니다!

13ff538

코드설명이 따로 필요하시다면 언제든 편하게 말씀해주세요

[yukyeongmin]

저는 두번째에서 125가 아니라 135인가 더 크게 나왔었어요.

[wjdgns7712]

저도 그리면서 해봤는데 잘모르겠어서 질문했는데 정훈님도 풀어봐 주셨군요!! 코드리뷰 자세히 해주시는것도 항상 감사해요!!
무지개 블록이랑 블록수는 많은게 우선이고, x,y는 작은게 우선이라 내림차순, 오름차순으로 처리 한건데 이부분이 틀린건가요?? 잘 이해가 안되네요ㅠㅠ

x,y는 블록그룹의 기준블록이 가장 작은값일뿐, 동일한 블록갯수인경우에는 기준블록이 가장 우측하단에있는 그룹블록을 제거하라고 문제조건에있습니다! 그래서 큰걸 골라주셔야합니다

[wjdgns7712]

아마 경민님이 짜신코드로 돌리면은
2번 TC에서 두번째에 (1,4)를 기준블록으로해서 지우지않나요?

[yess98]

@yukyeongmin

경민님 여기 조건 보시면 ,
“행 번호 큰것, 행번호 같다면 열번호 큰것” 우선으로 삭제해주셔야해요!! 정훈님 말씀하신대로 x,y를 내림차순으로 바꿔보세요:)

[yukyeongmin]

앗... 반대로 이해했군요... 감사합니다