> 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-20.md).

# 마법사 상어와 파이어 스톰

문제 잘못 이해한 부분

부분 격자로 나누고, 모든 부분 격자를 시계 방향으로 90도 회전하는 것인데, 문제에서 하이라이트 된 부분만 회전하는 줄 알고, 짝수/홀수 행으로 나눠서 생각을 했지만 그냥 부분 격자 크기 단위로 회전시키면 되는 거였다.\
잘못 생각한 부분 - 부분 격자 4x4일 때 각 부분 격자의 열 : 부분 격자 2^L\*2 주기로 생각함\
짝수행 : 0,1,2,3/8,9,10,11/16,17,18,19/...\
홀수행 : 4,5,6,7/12,13,14,15/20,21,22,23/...\
\=> 행과 열 모두 2^L 단위로 증가하기 때문에 2중 for문으로 구성하고 반복 변수가 증가하는 단위를 2^L로 하면 되는 거였음!!\
for(int i=0;i\<N;**i+=2^L**) {\
&#x20; for(int j=0;j\<N;**j+=2^L**) {

나의 문제 접근 방

격자의 바깥테두리부터 시작해서 상변, 우변, 하변, 좌변 한 싸이클을 돌고 나면 행과 열을 1씩 증가시켜 두번째 테두리, 세번째 테두리.. 를 회전시키고, 각 칸마다 방문체크배열을 통해 방문한 칸은 true로 마킹함으로써,  다음으로 회전시키려는 (a,a) 칸이 이미 회전시킨 칸이라면 회전을 종료한다.

**각 행은 열로 이동**하고, 각 열은 행으로 이동하기 때문에 현재 행에서의 인덱스와 이동하는 열의 인덱스를 저장하는 변수 2개가 필요하고, 변에 따라서 하나는 증가하고, 하나는 감소 할 수 있다.\
\=>이 부분에서 일관성 있게 규칙성을 찾지 못했다.

참고한 레퍼런스의 알고리즘

현재 (i,j)에서 아래 그림처럼 각 열에 대해 회전 연산한다. 0열, 1열, 2열, 3열은 각각 0행,1행,2행,3행이 된다.\
부분 격자 한 변을 size라고 하고, 편의상 size=4라고 하자. NxN 격자에서 size 단위로 부분 격자가 존재하고, 이 각각의 부분 격자에 대해서 회전연산을 하기 때문에 2중 for문 구성은 아래와 같다!⭐⭐\
**for(int i=0;i\<N;i+= size){**\
&#x20; **for(int j=0;j\<N;j+= size){**\
각 행에 대해서 부분 격자의 열은 0,1,2,3/4,5,6,7 이런식으로 구성된다.\
현재 (0,0)에 있다면 이 부분 격자에서 각 열은 0,1,2,3이다.\
**각 행에 대해 회전하는 부분 격자의 열 변수 c 범위 : j \~ j+size-1,j++  ⭐️⭐️⭐️⭐️⭐️**\
**c에 따라 회전하는 행 변수 r 범위 : i+size-1 \~ i, i-- ⭐️⭐️⭐️⭐️⭐️**

![](https://3269900549-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MIbwNq54Ge4eqsziHM7%2F-Mhhe8QiTf0fc6WnJhyA%2F-MhhfQfNaqanoMblX7Sm%2Fimage.png?alt=media\&token=3717d55e-6eda-4678-8ad6-683a0583ba06)

**반복문 구성 특징**

**열에 따라 행이 이동하기 때문에 기존의 for문과는 반대되는 2중 for문이다.**\
**현재 위치(r,c)와 이동할 위치(nr,nc) 총 4개의 변수와 4개의 반복문이 필요하다.**

```java
for(int i=0;i<N;i+= size){
  for(int j=0;j<N;j+= size){
    for(int c=j;c<j+size;c++){
      int nr = i;int nc = j;
        for(int r = i+size-1; r>=i;r--) {
           tmp[nr][nc++] = Map[r][c];
         }
         nr++;
     }
   }
}
```

함수 구현

1. 회전 함수
2. 얼음 녹이는 함수
3. 총 얼음 양 구하는 함수
4. 가장 큰 얼음이 차지하는 칸 구하는 함수 : 단지 번호 붙이기와 똑같은데 현재 큐 크기만큼만 탐색하도록 백트랙킹이 추가된 버전.\
   이 문제에서 N의 크기는 최대 2^6이다. 2차원 배열 전노드에 대해 BFS를 해버리면 각 (i,j)에 대해 NxN 시간 복잡도이고, 전체 NxN 칸 \* NxN 시간복잡도 = N^4 = 2^24 >> 1억이기 때문에 백트랙킹이 필수이다.