바깥 껍데기 부터 완탐 하기 (백준 16926. 배열 돌리기 1)

문제 분석

반시계 방향으로 돌아가는데, 빙글뱅글 달팽이가 아니라 맨 바깥 껍데기 돌아가고, 그 안쪽 껍데기가 돌아간다. 

고민한 것

• 코너에서 값 밀기를 어떻게 구현할 것인지
• 껍데기를 어떤 기준으로 나누어 완전 탐색할 것인지

코너에서 값을 미는 것의 경우 r 값이 달라지기 때문에 코너 마다 어떤 식으로 다음 좌표를 설정해주어야 할까?

껍데기는... 진짜 어떻게 나누지... 맨 바깥 한바퀴 돌고, 열이나 행을 하나 줄여서 안으로 들어가기를 반복하기?

풀이

for 문을 사용하여 상하좌우 변을 처리해줄 수 있었지만, 조건에 인덱스를 설정해주는 과정 실수할 가능성이 커서(복잡해서) 델타 탐색 방식을 사용했다. 방향 값만 dir 에 저장하여 꺾어줄 수 있었다. 하지만 "상단만 시계 방향으로 움직이기" 등의 독립 조건이 붙는다면 각각 변 단위로 처리해야 할 것이다.

static int[] dr = { 0, 1, 0, -1 };
static int[] dc = { 1, 0, -1, 0 }; // 우 하 좌 상

1. 위와 같이 방향을 설정한 이유

좌상단 arr[i][i]를 first 변수에 빼두면 그 자리는 빈칸이 된다. 생긴 빈칸을 채우기 위해 시계 반시계 방향으로 다음 값들을 당겨와야 한다.

• 우(0, 1) - arr[i][i] 빈칸을 채우기 위해 오른쪽(arr[i][i+1])에 있는 값을 가져온다 (상단 변 처리)
• 하(1, 0) - 오른쪽 끝까지 가서 생긴 빈칸을 채우기 위해 아래쪽에 있는 값을 가져온다. (우측 변 처리)
• 좌(0, -1) - 오른쪽 아래 끝에서 생긴 빈칸을 채우기 위해 왼쪽에 있는 값을 가져온다. (하단 변 처리)
• 상(-1, 0) - 왼쪽 아래 끝에서 생긴 빈칸을 채우기 위해 위쪽에 있는 값을 가져온다. (좌측 변 처리)

2. 만약 화살표 방향(이동 방향)대로 dr, dc를 잡는다면?

화살표가 가리키는 이동 순서는 하 우 상 좌 (반시계 방향) 이다. 이 순서대로 dr, dc를 짜려면, arr[next] = arr[current] 식으로 코드를 짜야 하는데, 이렇게 하면 다음에 옮겨야 할 값이 이미 덮어씌워져 버리는 문제가 발생한다. 그래서 "내가 비었으니 내 다음 놈(nr, nc)을 데려오겠다" 는 전략을 사용한다. 그 순서가 우 하 좌 상이다. 즉, 탐색은 시계 방향으로 하되 값은 당겨와서 갱신해서 반시계 방향으로 움직인 것처럼 한다.

 

핵심 로직

static void move() {
    int layers = Math.min(N, M) / 2;

    for (int i = 0; i < layers; i++) {
        int r = i;
        int c = i;

        int first = arr[r][c]; // 나중에 저장할 첫 번째 위치 값

        int dir = 0;

        while (dir < 4) {
            int nr = r + dr[dir];
            int nc = c + dc[dir];

            if (nr >= i && nr < N - i && nc >= i && nc < M - i) {
                arr[r][c] = arr[nr][nc];
                r = nr;
                c = nc;
            } else {
                dir++;
            }
        }

        arr[i + 1][i] = first;
    }
}

• 껍데기 수는 layers에 저장한다. 만약 2x10 배열에서 큰 수인 10을 기준으로 껍데기 수를 계산하면(5개) 실제로는 존재하지 않는 2층, 3층... 5층까지 파고들려고 하다가 인덱스 범위를 초과하게 된다.
• 그리고 한 개씩 값을 밀면서 마지막에 덧붙여야 하게 된 첫 번째 값을 저장해둔다.
• 모든 layers 를 돈다. 이때 (i, i) 는 껍데기의 시작점이다.

nr >= i && nr < N - i && nc >= i && nc < M - i

• i 부터 N - i, M - i 까지 탐색하는 것은 양 옆 각각 껍데기를 제외한 안쪽 껍데기 만큼의 범위를 표현해준다.