[LeetCode] 54. Spiral Matrix

 

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

Spiral Matrix - LeetCode

 

1. 문제

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

 

m x n만큼의 정수형 이차원 배열이 주어진다. 이를 통해서 회전 순서로 순회한 기록을 담은 일차원 배열을 반환하라.

 

2.Solution

사실, 이번에 처음 leetCode에서 submission을 낸 문제였으나 어느정도 코테를 준비하신 분들이라면 익숙한 향기가 느껴질 것이다?

 

먼저, 코드를 올리고 해당 코드를 기반으로 설명해보겠다.

var spiralOrder = function(matrix) {
    let directions = [[0,1],[1,0], [0,-1], [-1,0]];
    let result = [];
    let curDir = 0, r = 0, c = 0;
    result.push(matrix[0][0]);
    matrix[0][0] = -101;

    while(result.length != matrix.length * matrix[0].length){
        let curR = r + directions[curDir][0];
        let curC = c + directions[curDir][1];
        
        if((curR<0||curR>= matrix.length||curC<0||curC>=matrix[0].length)||matrix[curR][curC] === -101){
            curDir = (curDir+1)%4;
        }else{
            result.push(matrix[curR][curC]);
            matrix[curR][curC] = -101;
            r = curR, c = curC;
        }
    }
    return result;
};

 

먼저, 나는 문제를 유심히 봤을 때 이 문제에 다음과 같은 패턴이 존재한다고 생각했다.

- (0,0)에서부터 시작함.

- 오른쪽을 확인하고 벽을 만나거나 이미 탐색한 위치에 갈 것이라면 아래로 방향을 틀음.

- 아래쪽을 확인하고 벽을 만나거나 이미 탐색한 위치에 갈 것이라면 왼쪽으로 방향을 틀음.

- 왼쪽을 확인하다가 위의 조건에 동일하게 적용되면 위로 방향을 틀음.

- 위에서 돌다가 다시 왼 쪽으로 방향을 틀음.

 

그렇기에, [우, 하, 좌, 상] 방향을 저장한 directions 배열을 사용하기로 생각했고, 코드 확인 시 최 상단에 먼저 생성을 해주었다.

이후, 풀이는 간단한데 결과를 저장할 배열 result선언 이후에 result의 길이가 matrix에 있는 모든 요소의 갯수와 동일해질 때 까지 돈다.

말 그대로, 모든 요소를 다 볼 때까지 탐색을 진행한다는 뜻이다.

 

만약, matrix의 row, column의 범위를 초과하거나, 이미 간곳에 방문했을 경우, 방향을 꺾는다.

여기서, 이미 방문을 했는지의 여부는 hashSet을 사용할 수도 있겠지만, 나의 경우에는 -101로 matrix의 해당 위치에 표시했다.

 

이제, 모든 방향을 다 탐색하고 while문에서 나왔다면 완성이 된 result를 반환해주면 문제가 풀린다.