> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/undefined-1/undefined-24.md).

# 상어중학교

개괄적인 로직은 어느 정도 생각했다. 세부적인 조건이나 구현을 제대로 하지 못했다.

전체적인 구조 :\
메인이 되는 solve 함수를 구현하고, 무한루프로 아래 연산을 반복한다.\
1\. **findremoveBlock**() : 블록 그룹을 찾아서 블록을 제거, 점수 합산.\
  \=> 연산을 반복하는 조건이 되기 때문에, 블록 그룹을 탐색&제거 하면 true를 리턴하고, 그렇지 못하면 false를 리턴해서 전체 연산 반복을 종료한다!\
2\. **gravity**() : 좌표값들을 아래 방향으로 이동시킨다.\
  \=> 범위초과 체크, 블록이 없는 칸이면 1칸씩 이동을 반복 : 2차원 배열 순회하면서 2중 for문 안에 while문을 만들어 아래로 계속 이동하는 반복문을 구성했다.\
\=> 블록 삭제해서 없는 칸을 100이라고 한다면, M이하의 모든 칸들은 블록이 있는 칸들이기 때문에, 다음 칸의 배열 값이 M이하일 때만 아래로 이동시킨다.\
✅이동시킬 때 주의점! 배열 값 몇번 회전/이동시켜보니, **제일 마지막으로 변하는 값을 가장 먼저 처리**해줘야한다! 따라서, 가장 마지막 행에 있는 값이 마지막에 변화하기 때문에 감소 반복문으로 구현해야한다고 생각했다.\
3\. rotate() : 2차원 배열 반시계 방향 회전. 로직 이해✅(아주 쉽고 간단했음)

```
void solve()  {
    while(true) {
        if(findremoveBlock() == false) break;
        gravity();
        rotate();
        gravity();
    }
}
```

rotate() :

```java
private static void leftRotate() {
        int[][] mapClone = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                mapClone[i][j] = map[j][N-1-i];
            }
        }
        for (int i = 0; i < N; i++) {
            System.arraycopy(mapClone[i], 0, map[i], 0, N);
        }
    }
```

생각하지 못한 부분

크기가 가장 큰 블록 그룹을 찾아서 갯수를 세야하기 때문에 BFS를 해야겠다는 생각은 했지만, 어떻게 구현해야할지 감을 못 잡았었다.\
\=> 문제에서 정의하는 블록 그룹의 "기준 블록" : 블록그룹에서 무지개 블록이 아닌 블록 중, 행번호가 가장 작은 블록, 여러개면 열번호 가장 작은 블록이다. 따라서, 행과 열번호가 가장 작은 블록이기 때문에, 블록 그룹을 탐색하는 시작점을 의미한다!⭐️ 그리고, BFS를 계속해서 반복하는데, 이 때 블록 그룹 기준 블록이 BFS 시작점이 된다!

2차원 배열 회전 마스터

1. 정사각형 배열 NxN 회전\
   ① 90° 반시계 회전 : newMap\[i]\[j] = map\[j]\[N-1-i]

   ```java
   private static void leftRotate() {
           int[][] mapClone = new int[N][N];
           for (int i = 0; i < N; i++) {
               for (int j = 0; j < N; j++) {
                   mapClone[i][j] = map[j][N-1-i];
               }
           }
           for (int i = 0; i < N; i++) {
               System.arraycopy(mapClone[i], 0, map[i], 0, N);
           }
       }
   ```

   ② 90° 시계 회전 : newMap\[i]\[j] = map\[N-1-j]\[i]

   ```java
   private static void rightRotate() {
           int[][] mapClone = new int[N][N];
           for (int i = 0; i < N; i++) {
               for (int j = 0; j < N; j++) {
                   mapClone[i][j] = map[N-1-j][i];
               }
           }
           for (int i = 0; i < N; i++) {
               System.arraycopy(mapClone[i], 0, map[i], 0, N);
           }
       }
   ```

2. 직사각형 배열 NxM 회전(4x5 배열 회전 => 5x4배열) 핵심은 RxC => CxR이 되고, 반복문 구성 또한 변수 바뀐다는 것!

   ① 90° 반시계 회전 : newRect\[i]\[j] = reect\[j]\[C-1-i]\
   반복문 구성은 기존 정사각형 회전과 동일하게 새로운 배열 기준으로 행부터 차례대로 채워지고,&#x20;

   기존 정사각형 배열과 달라진 점이라면, 기존 배열에서 열 위치가 N-1-i에서 C-1-i로 바뀌었다. \
   기존 배열의 열 좌표를 기준으로, 제일 끝 열(C-1)부터 시작해서 새로운 배열 첫번째(0번째) 행부터 채우지기 시작하기 때문이다!

   1. ```java
      private static void leftRotate() {
          int[][] newRect = new int[rectC][rectR];//4*5 => 5*4
      		for(int i=0;i<rectC;i++) {//squareR = squareC 이므로 동일한 변수로 2중 반복문 구성.
      			for(int j=0;j<rectR;j++) {
      				newRect[i][j] = rect[j][rectC-1-i];//기존 : N-1-i에서 N이 기존 배열의 열(rectC)로 바뀌었다!
      			}
      		}
      }
      ```

   ② 90° 시계 회전

   1. ```java
      private static void rightRotate() {
          int[][] rightRect = new int[rectC][rectR];//4*5 => 5*4 
      		for(int i=0;i<rectC;i++) {//squareR = squareC 이므로 동일한 변수로 2중 반복문 구성.
      			for(int j=0;j<rectR;j++) {
      				rightRect[i][j] = rect[rectR-1-j][i];
      			}
      		}
      }
      ```

![NxM 배열 반시계 방향 90° 회전](https://3269900549-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MIbwNq54Ge4eqsziHM7%2F-MjHVRpbPpr6baGrMhNB%2F-MjHXVxzVcQsRGngmWrq%2Fimage.png?alt=media\&token=b2758c82-3d1d-4485-b3e4-b22c29915ccb)

2차원 배열 회전 로직 한줄 정리\
NxN 배열 회전하는 것을 기준으로 생각하면 생각을 확장하기 쉽다. 새로운 배열의 첫번째행부터 시작해서 채우는 인덱스로 반복문을 구성한다.(위의 그림 참고)\
반복변수 i,j 에 따라서 기존 배열에서 복사하는 행 또는 열 값이 고정되는 값이 존재하고, 변수에 따라서 기존 배열에서 변하는 인덱스값이 존재한다.\
\=>시뮬레이션 조금만 해보면 고정되는 인덱스, i,j에 따라 변하는 인덱스 알 수 있다!

![결과 확인](https://3269900549-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MIbwNq54Ge4eqsziHM7%2F-MjH_xovnRrZjIOJmbXK%2F-MjHa9X12uV4wB_UcHZe%2FScreen%20Shot%202021-09-11%20at%2011.03.12%20AM.png?alt=media\&token=bdbc7da9-b0e7-48a5-892a-e1b4462ae8d6)

솔루션\
문제에서 나온 오토플레이 동작 설명 그대로 구현대로 하면 된다.\
크기가 가장 큰 블록 그룹을 찾을 때, 크기가 동일하다면 포함된 무지개 칸 갯수가 가장 많은 것, 여러개면 행이 가장 큰 것, 그것도 여러개면 열이 가장 큰 것을 찾는다!

**문제 재정의, 추상화**

1. 2차원 배열 순회하면서 가장 큰 크기의 블록그룹 BFS 탐색! : 2중 for문, 큐 이용\
   문제 조건에 따라 검은색 블록(-1)은 포함하면 안 되고, 무지개 블록(0) 또는 일반 블록(M이하 자연수)만 해당된다.\
   **- 탐색 조건 시, 배열 값 체크 : 0보다 크고 M이하인지 확인한다! : 무지개인 칸은 왜 조건 체크안 해주지?🧐**\
   **=> 일단 일반 블록을 대상으로 탐색을 시작하고, 인접노드 방문하려 큐에 삽입할 때, 이 때 무지개인 칸 조건 넣어서 탐색해주도록 한다!**\
   기준 블록 : 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록! 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이기 때문에, 0이 아니고, **행과 열이 가장 작은 칸**이다.\
   \=>2차원 배열 순회하는 2중 for문에서 **처음**으로 나오는 0, -1이 아닌 좌표에 대해 기준 블록으로 설정해준다!\
   \=>기준 블록은 블록 그룹을 찾기 위한 탐색 시작점이 된다! (큐에 제일 처음 들어가는 좌표)
2. 최대 갯수 블록 그룹으로 갱신 : 블록 갯수, 무지개 블록 갯수, 기준 블록의 행값, 기준 블록의 열값 큰 것으로 갱신, 최대 갯수가 2개 이상인지 확인.
3. 점수 합산
4. 최종 갱신된 블록그룹에 속하는 블록들(좌표칸) 삭제 처리 : 6으로 마킹.