[BOJ 21609] 상어 중학교 - JAVA, Gold2

https://www.acmicpc.net/problem/21609

21609번: 상어 중학교

📌구현할 기능 목록

1. 격자 한 변의 크기, 색상의 개수와 각 격자 칸에 들어있는 블록의 정보를 입력받는다.

  - 격차 한 변의 크기 : 1~20

  - 색상의 개수 : 1~5

  - [블록의 정보] 검정 블록 : -1, 무지개 블록 : 0, 일반 블록 : 1~N

 

2. BFS 탐색을 통해 격자에서 가장 큰 블록 그룹을 찾는다.

  - 탐색으로 찾는 블록 그룹의 내부 블록 중, 무지개 블록이 아니면서

    행/열 블록의 번호가 최소인 블록은 기준 블록으로 한다.

  - 만약 블록 그룹의 크기가 동일하다면, 블록 그룹 내 무지개 블록이 가장 많은 블록을 찾는다.

  - 만약 무지개 블록의 개수까지 동일하다면, 기준 블록의 행 번호가 가장 큰 블록 그룹을 찾는다.

  - 만약 기준 블록의 행 번호까지 동일하다면, 기준 블록의 열 번호가 가장 큰 블록 그룹을 찾는다.

 

3. 2번에서 찾은 블록 그룹을 삭제하고, 해당 블록 그룹의 크기의 제곱의 수만큼의 점수를 획득한다.

  - 만약 2번에서 찾은 블록 그룹의 크기가 2 미만이라면, 3~7번 과정을 생략한다.

  - 삭제된 블록의 값을 -1, 0, 1~N의 수가 아닌 임의의 수로 변경하여 삭제된 블록임을 나타낸다.

 

4. 격자에 중력을 작용시켜, 삭제되어 빈 블록 위에 일반 블록이 있다면 위치를 뒤바꿔 이동시킨다.

  - 검은 블록은 중력을 작동시켜도 위치가 변경되지 않는다.

 

5. 격자를 반시계 방향으로 90도 회전시킨다.

 

6. 격자에 중력을 다시 작용시킨다.

 

7. 3~6번 과정을 반복한다.

 

8. 획득한 점수의 총합을 출력한다.

 

🛠 주요 로직

- 이차원 배열 회전

 

이차원 배열을 반시계 방향으로 90도 회전시켜야한다.

방법은 아래와 같다.

int arr[N][N], tmp_arr[N][N];

for(int i=0; i<N; i++){
	for(int j=0; j<N; j++) tmp_arr[size-1-j][i] = arr[i][j];
}

arr = tmp_arr;

 

 

<'틀렸습니다' 판정 주의사항>

 

- 무지개 블록의 방문 여부 초기화

 

무지개 블록은 어떤 일반 블록과도 하나의 블록 그룹에 묶일 수 있으므로,

한번의 BFS 탐색을 마친 후에 반드시 방문여부를 초기화 시켜줘야한다.

if(map[mx][my]==0){
    tempRainbowBlockSize++;
    rainbowList.add(new Position(mx,my));
}

...(생략)

for(Position position:rainbowList){
    visited[position.row][position.col]=false;
}

 

- 기준 값들을 적절한 위치에서 초기화

 

기준 블록의 행/열 번호나, 선택된 블록 그룹의 무지개 블록 개수 등의

기준 값들을 적절한 위치에서 초기화 시켜줘야한다.

⌨ 제출 코드

import java.io.*;
import java.util.*;

public class Main {

    static int N,M;
    static int map[][];

    static int dx[] = {-1,0,1,0};
    static int dy[] = {0,1,0,-1};

    static List<Position> blockSet = new ArrayList<>();
    static int rainbowBlockSize=0;
    static int standardRow=0;
    static int standardCol=0;
    static int totalScore=0;
    static boolean visited[][];
    static final int SPACE_NUMBER = -2;

    static class Position{
        int row;
        int col;

        public Position(int row,int col){
            this.row=row;
            this.col=col;
        }
    }

    static void removeBlock(){
        for(Position block:blockSet){
            int row = block.row;
            int col = block.col;
            map[row][col]=SPACE_NUMBER;
        }
        totalScore+=(int)Math.pow(blockSet.size(),2);
    }

    static void gravity(){
        for(int col=0;col<N;++col){
            for(int i=N-2;i>=0;--i){
                for(int j=i;j<N-1;++j){
                    if(map[j][col]==-1 || map[j][col]==SPACE_NUMBER) break;
                    if(map[j+1][col]==SPACE_NUMBER){
                        map[j+1][col]=map[j][col];
                        map[j][col]=SPACE_NUMBER;
                    }
                    else break;
                }
            }
        }
    }

    static void rotate(){
        int tempMap[][] = new int[N][N];
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                tempMap[i][j]=map[j][N-1-i];
            }
        }
        for(int i=0;i<N;++i){
            System.arraycopy(tempMap[i],0,map[i],0,tempMap[i].length);
        }
    }

    static void printMap(){
        for(int i=0;i<N;++i){
            for(int j=0;j<N;++j){
                System.out.printf("%2d ",map[i][j]);
            }
            System.out.println();
        }
    }

    static int bfs(int r,int c,int standardBlock){
        int blockSize=0;
        if(visited[r][c]) return blockSize;
        if(standardBlock==-1 || standardBlock==0 || standardBlock == SPACE_NUMBER){
            return blockSize;
        }
        Queue<Position> q = new LinkedList<>();
        q.offer(new Position(r,c));
        int tempRainbowBlockSize=0;
        int tempStandardRow=r;
        int tempStandardCol=c;
        visited[r][c]=true;
        List<Position> list = new ArrayList<>();
        List<Position> rainbowList = new ArrayList<>();
        list.add(new Position(r,c));
        blockSize++;

        while(!q.isEmpty()){
            Position now = q.poll();
            for(int i=0;i<4;++i){
                int mx = now.row+dx[i];
                int my = now.col+dy[i];

                if(mx<0 || mx>=N || my<0 || my>= N) continue;
                if(visited[mx][my]) continue;
                if(map[mx][my]==-1 || map[mx][my]==SPACE_NUMBER) continue;
                if(map[mx][my]!=0 && map[mx][my]!=standardBlock) continue;

                if(map[mx][my]==0){
                    tempRainbowBlockSize++;
                    rainbowList.add(new Position(mx,my));
                }

                if(map[mx][my]==standardBlock){
                    if(tempStandardRow>mx){
                        tempStandardRow=mx;
                        tempStandardCol=my;
                    }
                    else if(tempStandardRow==mx){
                        if(tempStandardCol>my){
                            tempStandardRow=mx;
                            tempStandardCol=my;
                        }
                    }
                }
                visited[mx][my]=true;
                q.offer(new Position(mx,my));
                list.add(new Position(mx,my));
                blockSize++;
            }
        }

        if(blockSize<2){
            return blockSize;
        }

        for(Position position:rainbowList){
            visited[position.row][position.col]=false;
        }

        if(blockSet.size()<list.size()){
            blockSet=new ArrayList<>(list);
            rainbowBlockSize=tempRainbowBlockSize;
            standardRow=tempStandardRow;
            standardCol=tempStandardCol;
        }
        else if(blockSet.size()==list.size()){
            if(rainbowBlockSize<tempRainbowBlockSize){
                blockSet=new ArrayList<>(list);
                rainbowBlockSize=tempRainbowBlockSize;
                standardRow=tempStandardRow;
                standardCol=tempStandardCol;
            }
            else if(rainbowBlockSize==tempRainbowBlockSize){
                if(standardRow<tempStandardRow){
                    blockSet=new ArrayList<>(list);
                    rainbowBlockSize=tempRainbowBlockSize;
                    standardRow=tempStandardRow;
                    standardCol=tempStandardCol;
                }
                else if(standardRow==tempStandardRow){
                    if(standardCol<tempStandardCol){
                        blockSet=new ArrayList<>(list);
                        rainbowBlockSize=tempRainbowBlockSize;
                        standardRow=tempStandardRow;
                        standardCol=tempStandardCol;
                    }
                }
            }
        }
        return blockSize;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());
            }
        }

        while(true){
            blockSet = new ArrayList<>();
            visited = new boolean[N][N];
            boolean isContinue=false;
            standardRow=0;
            standardCol=0;
            for(int i=0;i<N;++i){
                for(int j=0;j<N;++j){
                    if(bfs(i,j,map[i][j])>=2) isContinue=true;
                }
            }
            if(!isContinue) break;

            removeBlock();
            gravity();
            rotate();
            gravity();
        }

        bw.write(totalScore+"\n");
        bw.flush();
        bw.close();
    }
}