[LeetCode] 59. Spiral Matrix II - Java

https://leetcode.com/problems/spiral-matrix-ii/description/

Spiral Matrix II - LeetCode

---

문제

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

Example 1:

Input: n = 3
Output: [[1,2,3],[8,9,4],[7,6,5]]

Example 2:

Input: n = 1
Output: [[1]]

 

Constraints:

• 1 <= n <= 20

---

풀이

풀이 과정

정수 n이 주어질 때 n x x크기의 이차원배열을 1부터 n^2까지 나선형으로 채워야하는 문제이다

풀이하는 과정은 54. Sprial Matrix와 같다.
두 문제의 차이점은 Sprial Matrix는 이미 채워진 배열의 요소를 구하는 문제이고 Sprial Matrix II는 빈 배열을 처음부터 채워나가야 하는 것이다.

먼저 최종적으로 return할 2차원 배열을 생성한다.

// 정답 배열
int[][] answer = new int[n][n];

 

다음으로 각 요소들의 위치를 판단하기 위한 변수들을 선언한다.

정수 dir은 현재 이동방향을 나타내는 변수이며 0, 1, 2, 3 순서대로 오른쪽, 아래, 왼쪽, 위를 나타낸다.
정수 배열 dirR과 dirC는 각각 현재 이동방향에 대해서 행과 열의 이동 방향을 나타낸다.
마지막으로 정수 row와 col은 현재 탐색중인 행과 열의 좌표를 나타낸다. 시작점은 0, 0으로 설정한다.

// 현재 이동방향 (오른쪽, 아래, 왼쪽, 위)
int dir = 0;
// Row의 이동방향
int[] dirR = {0, 1, 0, -1};
// Column의 이동방향
int[] dirC = {1, 0, -1, 0};
// 시작 Row
int row = 0;
// 시작 Col
int col = 0;

 

해당 변수들을 가지고 정답 배열의 길이만큼 반복하며 탐색을 진행한다.
현재 행과 열에 1부터 차례대로 삽입하고 다음 이동할 좌표에 대해서 조건을 판단하여 이동방향을 변경해야한다.
이동방향을 변경해야하는 경우는 다음 두 가지이다.

1. 다음으로 이동할 좌표가 배열을 벗어난 경우
2. 이미 방문한 좌표인 경우

해당 조건에 해당하는 경우 이동방향을 변경하고 최종적으로 행과 열의 좌표값을 갱신한다.

// 정답 배열의 길이만큼 반복
for(int i = 0; i < n * n; i++) {
    answer[row][col] = i + 1;

    // 다음으로 이동할 좌표가 배열을 벗어나거나 이미 방문한 요소인 경우 이동방향을 변경
    if(row + dirR[dir] < 0 || row + dirR[dir] >= n ||
       col + dirC[dir] < 0 || col + dirC[dir] >= n ||
       answer[row + dirR[dir]][col + dirC[dir]] != 0) {
        dir = (dir + 1) % 4;
    }

    // 현재 좌표를 갱신
    row += dirR[dir];
    col += dirC[dir];
}

.

구해진 2차원 배열을 return한다.

return answer;

---

최종 코드

class Solution {
    public int[][] generateMatrix(int n) {
        // 정답 배열
        int[][] answer = new int[n][n];
        // 현재 이동방향 (오른쪽, 아래, 왼쪽, 위)
        int dir = 0;
        // Row의 이동방향
        int[] dirR = {0, 1, 0, -1};
        // Column의 이동방향
        int[] dirC = {1, 0, -1, 0};
        // 시작 Row
        int row = 0;
        // 시작 Col
        int col = 0;
        
        // 정답 배열의 길이만큼 반복
        for(int i = 0; i < n * n; i++) {
            answer[row][col] = i + 1;
            
            // 다음으로 이동할 좌표가 배열을 벗어나거나 이미 방문한 요소인 경우 이동방향을 변경
            if(row + dirR[dir] < 0 || row + dirR[dir] >= n ||
               col + dirC[dir] < 0 || col + dirC[dir] >= n ||
               answer[row + dirR[dir]][col + dirC[dir]] != 0) {
                dir = (dir + 1) % 4;
            }
            
            // 현재 좌표를 갱신
            row += dirR[dir];
            col += dirC[dir];
        }

        return answer;
    }
}

---