[10주차_월요일] 회전하는 빙하

[yeahdy]

• 사이트 : 코드트리(CT)
• 문제: 회전하는 빙하
• 년도: 2020

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[KodaHye]

🤔 시간복잡도 고려사항

• 2 ≤ n: 회전 가능 레벨 ≤ 6
• 1 ≤ q: 회전 횟수 ≤ 1,000
• 0 ≤ 얼음의 양 ≤ 100
• 0 ≤ 회전 레벨 ≤ n
• 배열의 최대 크기: 32 * 32
• 문제에 주어진 대로 구현해도, 시간 넉넉함

💡 풀이 아이디어

Level에 따라 화전하는 정도가 달라지나, 규칙은 동일함 (2L * 2L 만큼 선택하여 2L−1 * 2L−1만큼 잘라 4등분하여 회전)

• void rotate(int level)
  • 입력받은 level에 따라서 회전을 하는 함수
  • int[][] tmp: map의 1사분면 부분을 저장하는 변수
  • copyPart1(r, c, size / 2)을 통해 map에서 1사분면을 저장함
• void rotate(int r, int c, int dir, int level, int[][] tmp)
  • r, c: 배열에서 회전을 시작하는 지점
  • rr, cc: 첨부한 사진에서 민트색 부분 배열
  • level2에서는 표시되었지만, level1에서는 크기가 1 * 1이기 때문에 표시하지 않음
• void checkMapStatus()
  • bfs를 통해 map의 상태를 확인하며 얼음이 있는 영역의 최대 크기와 남아있는 얼음의 양 구하기

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ n ≤ 6
• 1 ≤ q ≤ 1,000
• 구현 문제라 딱히 신경쓰지 않았음

💡 풀이 아이디어

• 빙하 회전 → 빙하 녹음을 반복
• rotate(): 빙하의 회전을 구현
  • 2^level의 덩어리들 속에서 빙하의 움직임이 이루어짐
  • move(): 각 꼭짓점을 기준으로 다음 위치로 이동

    for (int i = 0; i < m; i += M) {
      for (int j = 0; j < m; j += M) {
          // 각 꼭짓점을 기준으로 덩어리들이 움직임
          move(i, j, N, 0);
          move(i, j + N, N, 1);
          move(i + N, j, N, 2);
          move(i + N, j + N, N, 3);
      }
    }

• 빙하의 상하좌우를 확인하여 빙하가 녹는 조건인지 체크하고 녹는 것 구현
• 모든 회전 및 녹는 과정이 끝나면 BFS
  • 총 빙하의 합 계산
  • 최대 군집의 크기 계산

    다혜님이 그림으로 너무 잘 표현해주셨네요

[icegosimperson]

🤔 시간복잡도 고려사항

• 빙하 회전 O(2)^n)^2), 얼음 녹이기 O(2^n)^2), BFS : O(2^n^2)
• O(2^n^2) * q
• 2 ≤ n ≤ 6, 1 ≤ q ≤ 1,000 -> 구현 가능

💡 풀이 아이디어

1) 격자 회전

• 회전 가능 레벨 n에 따라 격자의 크기 결정 (2^n * 2^n)
• 회전 횟수q와 회전 레벨을 받아서 회전

2) 빙하 회전

• 2^L 2L크기의 하위 격자로 나누어 회전
• 시계 방향으로 90도 회전
• 회전된 결과를 nextboard 배열에 복사 3) 얼음 녹이기
• 얼음이 상하좌우에 3개미만 인접하면 -1, 인접하면 유지
• 배열에 결과를 저장한 후 원래 배열에 복사 4) 남은 빙하 총량 계산 5) 가장 큰 얼음 군집 크기 계산
• BFS를 통해 격자 모든 칸 탐색, 연결된 얼음 칸들의 군집 크기 계산
• 군집 크기 중 max값 출력

[baexxbin]

🤔 시간복잡도 고려사항

• 2 ≤ n ≤ 6
• 1 ≤ q ≤ 1,000
• 0 ≤ 얼음의 양 ≤ 100
• 0 ≤ 회전 레벨 ≤ n
• 구현문제로 딱히 생각하지 않음

💡 풀이 아이디어

• 빙하 회전

  • 기존 90도 회전에서, 각 서브 사각형(분할된 배열)이 회전하는 형태로 업데이트

    private static void rotateIce(int sx, int sy, int l, int[][] tmp) {         // 레벨 사각형안의 분할된 사각형의 회전
    int s = 1<<l;
    int ss = 1 << (l - 1);
    
    for (int i = sx; i < sx + s; i+=ss) {                   // 현재 레벨 사각형의 시작 꼭짓점부터 진행
        for (int j = sy; j < sy + s; j+=ss) {
            int ox = i - sx;                                // 0점 맞추기
            int oy = j - sy;
            int rx = oy;                                    // 회전 좌표
            int ry = s-ox-ss;
           for (int x = 0; x < ss; x++) {                   // 분할된 사각형 조각 이동
                for (int y = 0; y < ss; y++) {
                    int cx = i + x;                         // 원본 배열에서 현재 위치
                    int cy = j + y;
                    int nx = rx + x;                        // 회전된 좌표에서 새로운 위치
                    int ny = ry + y;
                    tmp[nx+sx][ny+sy] = board[cx][cy];      // 회전된 위치엔 보정으로 뺐던 시작값 더해주기
                }
            }
        }
    }
    }

  • ry좌표 : 분할된 사각형 크기만큼의 조정이 필요
  • x,y for문 : 회전한 위치로 분할된 사각형 이동
• 얼음군집 구하기
  • bfs 수행하면서 얼음의 값과 최대 군집크기 갱신
  • 회전 끝나고 얼음 녹기 (문제 똑바로 읽기)

[yeongleej]

🤔 시간복잡도 고려사항

• 배열크기 2^n, n<= 6, 최대 N= 2^6 -> N * N

=> bfs 탐색: O(N* N)이므로 완전탐색 가능 => 시뮬레이션 가능

💡 풀이 아이디어

• 회전하기

public static void rotate(int S, int sx, int sy) {
    int ts = S / 2;
    for(int x=sx; x<sx+S; x+=ts) {
        for(int y=sy; y<sy+S; y+=ts) {
            int ox = x - sx;                              // 원점 이동
            int oy = y - sy;
            int nx = oy;                                  // 시계방향 회전
            int ny = S - ts - ox;
            t[nx+sx][ny+sy] = g[x][y];                   // 회전된 새로운 시작점 위치
            int tx = (nx+sx)-x;                               //  새로운 시작점 위치의 이동 벡터 구하기
            int ty = (ny+sy)-y;

                        // 내부 사각형 원소들 새로운 시작점 기준으로  덩어리 이동
            for(int i=x; i<x+ts; i++) {
                for(int j=y; j<y+ts; j++) {
                    t[i+tx][j+ty] = g[i][j];
                }
            }
        }
    }
}

• 빙하 총량 및 얼음 군집 구하기
  • bfs 활용

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 구현 + BFS
• 시간복잡도: 2 ≤ n ≤ 6 n*n = 36 1 ≤ q ≤ 1,000 문제의 요구사항에 따라 완전탐색 가능

💡 풀이 아이디어

1. 얼음 회전하기

   1. 회전한 얼음을 저장하기 위한 임시 배열 생성
   2. level 에 따라 2^L−1* 2^L−1 만큼 4등분
   3. 나뉜 구간 별로 회전을 위해 계산된 레벨을 활용해서 각 왼쪽 윗 모서리를 기준점으로 잡음. 왼쪽위 > 오른쪽위으로 이동 오른쪽위 > 오른쪽아래로 이동 오른쪽아래 > 왼쪽아래 왼쪽아래 > 왼쪽위로 이동
   4. 각 구간 별로 얼음 회전하기 나뉜 구간 안에서 정해진 방향성을 따라 계산된 레벨 만큼 회전 (1레벨:1번, 2레벨:4번, 3레벨:8번)
   5. 얼음을 모두 회전한 후 임시 배열 > 원본 배열로 복사

2. 얼음 녹이기 상하좌우 완전탐색을 통해 3개 미만일 경우 얼음 녹이기

3. 얼음 군집 계산하기 BFS 탐색을 통해 이어진 얼음 군집의 최대치 계산하기

얼음 군집을 BFS 로 방향 탐색할 때 1개는 군집으로 포함되지 않는 부분 현재 위치에 대한 얼음의 크기와 방문처리 조건문 처리를 제대로 못해서 헤맸네요...