[LeetCode] 54. Spiral Matrix - Java

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

Spiral Matrix - LeetCode

---

문제

Given an m x n matrix, return all elements of the matrix in spiral order.

 

Example 1:

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

Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100

---

풀이

풀이 과정

m*n 크기의 2차원 배열 matrix가 주어질 때 배열의 요소들을 나선방향으로 돌면서 구하는 문제이다.

우선 풀이에 필요한 변수들을 선언한다.

// 행의 길이
int m = matrix.length;
// 열의 길이
int n = matrix[0].length;
// matrix 배열의 요소 개수 크기만큼의 정답 배열 선언
List<Integer> answer = new ArrayList<>();
// 방향에 따라 이동할 x,y좌표 값
// 오른쪽, 아래, 왼쪽, 위
int[] dirX = {0, 1, 0, -1};
int[] dirY = {1, 0, -1, 0};
// 방향을 나타낼 포인터
int dir = 0;
// 시작 x좌표
int x = 0;
// 시작 y좌표
int y = 0;

 

matrix 배열 요소의 길이만큼 반복하며 탐색 한다.
현재 탐색중인 좌표의 값을 정답 리스트에 추가하고 방문 여부를 체크하기위해 배열요소의 최대값인 100보다 큰 값으로 현재 요소 값을 변경한다.
그 후 이동할 방향에 따라 이동한 x,y 좌표가 배열을 벗어나거나 이미 방문한 요소인 경우에는 방향을 변경한다.
방향이 결정된 후에 x와 y좌표를 갱신한다.

// matrix 배열 요소의 길이만큼 탐색
for(int i = 0; i < m * n; i++) {
    // 현재 좌표의 값을 정답 리스트에 추가
    answer.add(matrix[x][y]);
    // 방문 여부를 체크하기위해 배열요소의 최대값인 100보다 큰 값으로 현재 요소값 변경 
    matrix[x][y] = 101;

    // 이동한 좌표가 배열을 벗어났거나 이미 방문한 요소인 경우
    if(x + dirX[dir] < 0 || x + dirX[dir] >= m || y + dirY[dir] < 0 || y + dirY[dir] >= n || matrix[x + dirX[dir]][y + dirY[dir]] > 100) {
        // 방향을 변경
        dir = (dir + 1) % 4;
    }

    // 좌표 갱신
    x = x + dirX[dir];
    y = y + dirY[dir];
}

 

최종적으로 구한 정답 리스트를 return한다.

return answer;

---

최종 코드

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // 행의 길이
        int m = matrix.length;
        // 열의 길이
        int n = matrix[0].length;
        // matrix 배열의 요소 개수 크기만큼의 정답 배열 선언
        List<Integer> answer = new ArrayList<>();
        // 방향에 따라 이동할 x,y좌표 값
        // 오른쪽, 아래, 왼쪽, 위
        int[] dirX = {0, 1, 0, -1};
        int[] dirY = {1, 0, -1, 0};
        // 방향을 나타낼 포인터
        int dir = 0;
        // 시작 x좌표
        int x = 0;
        // 시작 y좌표
        int y = 0;
        
        // matrix 배열 요소의 길이만큼 탐색
        for(int i = 0; i < m * n; i++) {
            // 현재 좌표의 값을 정답 리스트에 추가
            answer.add(matrix[x][y]);
            // 방문 여부를 체크하기위해 배열요소의 최대값인 100보다 큰 값으로 현재 요소값 변경 
            matrix[x][y] = 101;
            
            // 이동한 좌표가 배열을 벗어났거나 이미 방문한 요소인 경우
            if(x + dirX[dir] < 0 || x + dirX[dir] >= m || y + dirY[dir] < 0 || y + dirY[dir] >= n || matrix[x + dirX[dir]][y + dirY[dir]] > 100) {
                // 방향을 변경
                dir = (dir + 1) % 4;
            }
            
            // 좌표 갱신
            x = x + dirX[dir];
            y = y + dirY[dir];
        }

        return answer;
    }
}

---