[BOJ] 21609 상어 중학교 - Java

✨ 구현 & BFS

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

21609번: 상어 중학교

---

📍 고려해야할 점

• 그룹에 속하는 블록의 조건 
  • 일반 블록이 적어도 하나 이상
  • 일반 블록의 색은 모두 같아야함
  • 검은색 블록 포함 X
  • 무지개색 블록은 몇개든 상관 X
  • 블록의 개수는 2개 이상
  • 블록 그룹의 기준 블록 = 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록. 그러한 블록이 여러 개이면 열의 번호가 가장 작은 블록 ..

 

• 오토플레이 기능 ➔ 블록 그룹이 없을 때까지 반복 
  1. 크기가 가장 큰 블록 그룹 찾기
     ➔ 그러한 블록 그룹이 여러 개면 블록 그룹에서 무지개 블록이 가장 많은 블록 그룹 선택 
     ➔ 그러한 블록 그룹도 여러 개면 기준 블록의 행이 가장 큰 것 선택 
     ➔ 그러한 블록 그룹 또한 여러 개면 열이 가장 큰 것 선택
  2. 1번에서 찾은 블록 그룹의 모든 블록 제거하고, 블록 그룹에 포함된 블록의 수=B라 할 때, B의 제곱만큼 점수 획득
  3. 격자에 중력 작용 ➔ 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 다른 블록이나 격자의 경계를 만날 때까지 이동
  4. 격자를 90도 반시계방향 회전시키기
  5. 다시 격자에 중력 작용

👉 고려해야할 조건들이 많다...

 

 

 

🕹️ 풀이 과정

• findBlockGroup() ➔ 블록 그룹 찾는 메소드
• bfs() ➔ 블록 그룹 찾는 메소드 
• gravity() ➔ 중력 작용하는 메소드 
• rotate() ➔ 격자를 90도 반시계방향으로 회전
• remove() ➔ 블록 그룹의 블록들을 제거하는 메소드 

👉 4~5개의 메소드로 작성할 수 있다. 

---

우선, 좌표에 대한 정보와 블록 그룹에 대한 정보를 따로 담을 수 있는 클래스를 각각 만들 것이다.

 

🔸 Group : 블록그룹의 정보

static class Group implements Comparable<Group> {
    int x, y, totalCnt, rainbowCnt;

    public Group(int x, int y, int totalCnt, int rainbowCnt) {
        this.x=x;
        this.y=y;
        this.totalCnt=totalCnt;
        this.rainbowCnt=rainbowCnt;
    }

    // 무지개블록 개수 & 행 & 열 --> 내림차순 정렬
    @Override
    public int compareTo(Group o) {
        if(totalCnt==o.totalCnt) {
            if (rainbowCnt == o.rainbowCnt) {
                if (x == o.x) {
                    return o.y - y;
                } return o.x - x;
            }return o.rainbowCnt-rainbowCnt;
        }return o.totalCnt-totalCnt;
    }
}

 

compareTo() 메소드에 오토플레이 기능 #1의 조건들(블록 그룹 선택 조건)을 작성해준 것이다. 

 

 

🔸 Info  : 좌표 정보

static class Info{
    int x, y;

    public Info(int x, int y) {
        this.x=x;
        this.y=y;
    }
}

 

보통 배열을 사용해서 arr[0]에 행의 값을, arr[1]에 열의 값을 넣어 사용하기도 하지만

개인적으로 나는 클래스를 따로 정의해서 사용하는 것이 더 편리하다고 느껴 좌표 정보 클래스도 생성했다. 

 

 

🔹findBlockGroup()  : 블록 그룹 찾기

 

static boolean findBlockGroup(){
	visit = new boolean[N][N];
    list = new ArrayList<>(); // Group을 담을 리스트

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (!visit[i][j] && board[i][j] > 0) {
                bfs(i, j, true);
            }
        }
    }
    
    visit = new boolean[N][N]; // 블록그룹에 속한 블록들을 찾아야하기 때문에 다시 초기화시킨다.
    if(list.isEmpty()) return false; // 블록그룹을 만들 수 없다면 false 반환
    else{
    	Collections.sort(list); // Group의 compareTo에 따라 정렬됨.
        bfs(list.get(0).x,list.get(0).y, false);
        remove();
    }
    return true;
}

 

 

🔹 bfs() : 블록 그룹 본격적으로 찾기 

public static void bfs(int x, int y, boolean flag){
	int rainbow = 0;
    int cntBlock = 1;
   
    Queue<Info> queue = new LinkedList<>();
    queue.add(new Info(x, y));
    visit[x][y] = true;

    while (!queue.isEmpty()) {
        Info now = queue.poll();

        for (int i = 0; i < 4; i++) {
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visit[nx][ny]) {
            	// 블록 그룹의 색이 같거나 무지개색이면 ㅇㅋ
                if(board[nx][ny]==0 || board[nx][ny]==board[x][y]){
                    visit[nx][ny] = true;
                    if(board[nx][ny]==0) rainbow++;
                    queue.add(new Info(nx, ny));
                    cntBlock++;
                }
            }
        }
        
        // 블록그룹의 블록 개수가 2개 이상이라면 ㅇㅋ
        // 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 열의 번호가 가장 작은 블록 
        // -> 순차적으로 탐색하기 때문에 따로 고려하지 않아도 됨 
        if(cntBlock>=2) list.add(new Group(x, y, cntBlock, rainbow));
        
        // flag가 false라면 블록을 제거할 단계를 거칠 것임. 
        // flag가 true라면 블록그룹을 탐색하는 단계를 거칠 것임 
        // -> 무지개색인 블록은 다른 블록그룹에 또 속할 수도 있기 때문에 재방문 가능하도록 visit을 false로 되돌린다.
        if(flag){
        	for(int i=0; i<N; i++){
            	for(int j=0; j<N; j++){
             		if(board[i][j]==0) visit[i][j]=false;   
                }
            }
        }
    }
}

 

 

🔹 remove() : 선택된 블록그룹의 블록들 제거하기

 

블록들의 개수의 제곱만큼 점수에 더한다. 

public static void remove(){
	int cnt=0;
    for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
     		if(visit[i][j]){
            	cnt++;
                board[i][j] = -2; // -2로 빈칸을 표시
            }
        }
    }
    score+=(cnt*cnt);
}

 

 

🔹 rotate()  :  격자를 반시계방향으로 90도 회전시키기

격자를 반시계방향으로 90도 회전시키면 위의 그림과 같다.

규칙을 찾아보면,

(0, 0) ➔ (3, 0)

(0, 1) ➔ (2, 0)

(0, 2) ➔ (1, 0)

(0, 3) ➔ (0, 0)

 

(1, 0) ➔ (3, 1)

(2, 0) ➔ (3, 2)

(3, 0) ➔ (3, 3) ...

 

왼쪽이 회전시키기 전의 좌표이고, 오른쪽이 회전시킨 후의 좌표이다.

(i, j) ➔ (ni, nj)라 할 때, nj=i 이고, ni = (N-1)-j 이다. (N은 격자의 가로, 세로 크기)

public static void rotate(){
    int[][] tmp = new int[N][N];

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

 

 

 

🔹 gravity()  : 중력 작용하기

중력이 작용하면 위의 그림과 같이 블록들이 이동한다.

밑으로 쭉 내려보낸다고 생각하면 된다. 

 

static void gravity(){
    for (int i = N-1; i >=0; i--) {
        for (int j = 0; j < N; j++) {
            if (board[i][j]>=0) {
                int ni=i;
                while (true) {
                	ni++;
                    if (ni>=N || board[ni][j] != -2) break;
                }
                ni--;
                if(ni!=i){
                    board[ni][j] = board[i][j];
                    board[i][j]=-2;
                }
            }
        }
    }
}

 

 

👩‍💻 전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_21609_상어중학교 {

    static int N, M, score;
    static int[][] board;
    static boolean[][] visit;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static List<Group> list = new ArrayList<>();

    static class Group implements Comparable<Group> {
        int x, y, totalCnt, rainbowCnt;

        public Group(int x, int y, int totalCnt, int rainbowCnt) {
            this.x=x;
            this.y=y;
            this.totalCnt=totalCnt;
            this.rainbowCnt=rainbowCnt;
        }

        // 무지개블록 개수 & 행 & 열 --> 내림차순 정렬
        @Override
        public int compareTo(Group o) {
            if(totalCnt==o.totalCnt) {
                if (rainbowCnt == o.rainbowCnt) {
                    if (x == o.x) {
                        return o.y - y;
                    } return o.x - x;
                }return o.rainbowCnt-rainbowCnt;
            }return o.totalCnt-totalCnt;
        }
    }
    static class Info{
        int x, y;

        public Info(int x, int y) {
            this.x=x;
            this.y=y;
        }
    }

    static boolean findBlockGroup(){
        visit = new boolean[N][N];
        list = new ArrayList<>(); // Group을 담을 리스트

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (!visit[i][j] && board[i][j] > 0) {
                    bfs(i, j, true);
                }
            }
        }

        visit = new boolean[N][N]; // 블록그룹에 속한 블록들을 찾아야하기 때문에 다시 초기화시킨다.
        if(list.isEmpty()) return false; // 블록그룹을 만들 수 없다면 false 반환
        else{
            Collections.sort(list); // Group의 compareTo에 따라 정렬됨.
            bfs(list.get(0).x,list.get(0).y, false);
            remove();
        }
        return true;
    }

    // ** 블록 --> 검은 블록 포함 X && 일반 블록은 모두 동일 (적어도 하나 이상) && 무지개 블록은 상관 X
    // #1. 가장 큰 블록 찾기 --> 블록 개수 -> 무지개 블록 개수 -> 기준 블록의 행 (가장 큼) -> 기준 블록의 열 (가장 큼)
    public static void bfs(int x, int y, boolean flag){
        int rainbow = 0;
        int cntBlock = 1;
        visit[x][y] = true;

        Queue<Info> queue = new LinkedList<>();
        queue.add(new Info(x, y));

        while (!queue.isEmpty()) {
            Info now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];

                if (nx >= 0 && ny >= 0 && nx < N && ny < N && !visit[nx][ny]) {
                    // 블록 그룹의 색이 같거나 무지개색이면 ㅇㅋ
                    if(board[nx][ny]==0 || board[nx][ny]==board[x][y]){
                        visit[nx][ny] = true;
                        if(board[nx][ny]==0) rainbow++;
                        queue.add(new Info(nx, ny));
                        cntBlock++;
                    }
                }
            }
        }
        // 블록그룹의 블록 개수가 2개 이상이라면 ㅇㅋ
        // 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 열의 번호가 가장 작은 블록
        // -> 순차적으로 탐색하기 때문에 따로 고려하지 않아도 됨
        if(cntBlock>=2) list.add(new Group(x, y, cntBlock, rainbow));

        // flag가 false라면 블록을 제거할 단계를 거칠 것임.
        // flag가 true라면 블록그룹을 탐색하는 단계를 거칠 것임
        // -> 무지개색인 블록은 다른 블록그룹에 또 속할 수도 있기 때문에 재방문 가능하도록 visit을 false로 되돌린다.
        if(flag){
            for(int i=0; i<N; i++){
                for(int j=0; j<N; j++){
                    if(board[i][j]==0) visit[i][j]=false;
                }
            }
        }
    }

    public static void remove(){
        int cnt=0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(visit[i][j]){
                    cnt++;
                    board[i][j] = -2; // -2로 빈칸을 표시
                }
            }
        }
        score+=(cnt*cnt);
    }

    // #3. 중력 작용 -> 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동
    public static void gravity(){
        for (int i = N-1; i >=0; i--) {
            for (int j = 0; j < N; j++) {
                if (board[i][j]>=0) {
                    int ni=i;
                    while (true) {
                        ni++;
                        if (ni>=N || board[ni][j] != -2) break;
                    }
                    ni--;
                    if(ni!=i){
                        board[ni][j] = board[i][j];
                        board[i][j]=-2;
                    }
                }
            }
        }
    }

    // #4. 90도 반시계방향 회전
    public static void rotate(){
        int[][] tmp = new int[N][N];

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



    public static void main(String[] args) throws Exception {
        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());
            }
        }

        while(true){
            if (!findBlockGroup()) break;
            gravity();
            rotate();
            gravity();
        }
        System.out.println(score);
    }
}