65일 (885. Spiral Matrix III) matrix

You start at the cell (rStart, cStart) of an rows x cols grid facing east. The northwest corner is at the first row and column in the grid, and the southeast corner is at the last row and column.

You will walk in a clockwise spiral shape to visit every position in this grid. Whenever you move outside the grid's boundary, we continue our walk outside the grid (but may return to the grid boundary later.). Eventually, we reach all rows * cols spaces of the grid.

Return an array of coordinates representing the positions of the grid in the order you visited them.

 

Example 1:

Input: rows = 1, cols = 4, rStart = 0, cStart = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

Input: rows = 5, cols = 6, rStart = 1, cStart = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

 

Constraints:

• 1 <= rows, cols <= 100
• 0 <= rStart < rows
• 0 <= cStart < cols

 

 

- 접근방법

example 2번 그림을 참고.

 

1. 그림의 실선은 저장해야 할 유효한 인덱스로 보고, 점선의 경우 저장하지 말아야 할 인덱스 외부 범위로 생각하였다.

2. 이차원배열 내부만 나선형으로 순회하게 할 아이디어가 안 떠오르기 때문에 현재 지정한 (rStart, cStart)를 기준으로 나선형으로 끝없이 돌면서 점선에 해당하는 (6*5)인 30개의 유효인덱스를 모두 2차원배열에 저장하였다면 종료할 것이다.

 

3. 기준점부터 우-하-좌-상 4방향으로 나선형으로 돌면서 특정한 규칙을 발견하였다.

위 그림처럼 우측과 하측으로는 홀수만큼, 좌측 상측으로는 짝수만큼 도는 범위가 증가하는 것을 발견하였다.

때문에 (우-하 // 좌-상)의 사이에 나선형으로 도는 범위를 지정하는 변수 n을 사용하였다.

 

 

4. 정리하자면,

- 현재 지정한 (rStart, cStart)를 기준으로 나선형으로 끝없이 돌면서 점선에 해당하는 (6*5)인 30개의 유효인덱스를 모두 2차원배열에 저장하였다면 종료할 것이다.

- 유효한 인덱스(실선)에 해당할 경우만 저장할 것이지만, 유효하지않은 인덱스(점선)의 경우도 순회는 한다.

- 유효하지 않은 인덱스도 순회는 하므로, 현재 좌표를 기억 할 변수 (x, y)도 필요하다.

 

 

- 코드

class Solution {
    public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int[][] answer = new int[rows * cols][2];
        int cnt = 0;
        int n = 1;
        int x = rStart;
        int y = cStart;

        while (cnt < rows * cols) {

            for (int i = cStart; i < cStart + n; i++) {
                if(x < rows && y < cols && x >= 0 && y >= 0) {
                    answer[cnt][0] = x;
                    answer[cnt][1] = y;
                    ++cnt;
                }
                y++;
            }
            cStart = y;

            for (int i = rStart; i < rStart + n; i++) {
                if(x < rows && y < cols && x >= 0 && y >= 0) {
                    answer[cnt][0] = x;
                    answer[cnt][1] = y;
                    ++cnt;
                }
                x++;
            }
            rStart = x;
            n++;

            for (int i = cStart; i > cStart - n; i--) {
                if(x < rows && y < cols && x >= 0 && y >= 0) {
                    answer[cnt][0] = x;
                    answer[cnt][1] = y;
                    ++cnt;
                }
                y--;
            }
            cStart = y;

            for (int i = rStart; i > rStart - n; i--) {
                if(x < rows && y < cols && x >= 0 && y >= 0) {
                    answer[cnt][0] = x;
                    answer[cnt][1] = y;
                    ++cnt;
                }
                x--;
            }
            rStart = x;
            n++;

        }

        return answer;
    }
}

 

- while문은 접근방법2에 해당한다.

- cnt는 저장할 유효인덱스의 개수에 해당한다.

- x, y는 현재 위치를 기억하는 좌표이다.

- 4개의 for문은 각각  우-하-좌-상으로 나선형 이동에 각각 해당한다.

- n은 접근방법3의 규칙에 이용되는 나선형 이동에 범위를 지정하는 변수이다.