마법사 상어와 파이어 스톰

문제 잘못 이해한 부분

부분 격자로 나누고, 모든 부분 격자를 시계 방향으로 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) { 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){ 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-- ⭐️⭐️⭐️⭐️⭐️

반복문 구성 특징

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

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억이기 때문에 백트랙킹이 필수이다.