[LeetCode] 54. Spiral Matrix

문제 출처: https://leetcode.com/problems/spiral-matrix/

Spiral Matrix - LeetCode

---

문제

$m \times n$ $martix$의 모든 원소를 나선 순서로 반환하라.

예제

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

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]

---

풀이

행렬을 나선형으로 탐색을 수행할 때, 탐색 순서를 도식화하면 아래의 그림과 같습니다. 

행렬의 최외곽(파란선)을 훑고 나서, 다음 외곽(주황선)을 훑는 식으로 진행이 됩니다.

 

주어진 행렬의 외곽만 탐색하는 알고리즘이 존재한다고 가정하면, 행렬의 크기를 줄여가며 외곽 탐색 알고리즘을 반복 수행하는 것으로 원하는 답을 얻을 수 있을 것이라 기대할 수 있습니다.

 

행렬의 외곽을 탐색하는 알고리즘을 작성해봅시다. 위 그림을 토대로 생각해보면, 두 가지 정보만 있으면 외곽 탐색을 수행할 수 있을 것 같습니다. 

• 시작 위치: (0, 0)
• 끝 위치: (m, n)

이 두 가지 정보를 토대로 외곽 탐색의 각 꼭짓점을 찾을 수 있기 때문입니다.

// 시작: (startRow, startCol)
// 끝: (endRow, endCol)
var searchOutline = function(matrix, startRow, endRow, startCol, endCol) {
    let result = [];
    
    // 상단 탐색
    for (let col = startCol; col <= endCol; col++) {
    	result.push(matrix[startRow][col]);
    }
    
    // 우측 탐색
    for (let row = startRow+1; row <= endRow; row++) {
        result.push(matrix[row][endCol]);
    }   
    
    // 하단 탐색
    if (endRow > startRow) {
      for (let col = endCol-1; col >= startCol; col--) {
          result.push(matrix[endRow][col]);
      }
    }
    
    // 좌측 탐색
    if (endCol > startCol) {
    	for (let row = endRow-1; row > startRow; row--) {
          result.push(matrix[row][startCol]);
      }
    }
    
    return result;
}

이 알고리즘에서 주의해야 할 점은 하단과 좌측을 탐색하기 전, 탐색하려는 행 또는 열이 이전 상단과 우측을 탐색하면서 탐색하지는 않았는지 체크하는 것입니다.

 

이제 남은 작업은 탐색 범위를 줄여가면 외곽 탐색 알고리즘을 반복하는 것입니다.

var spiralOrder = function(matrix) {
    let answer = [];
    
    const N = matrix.length;
    const M = matrix[0].length;
    
    let startRow = 0,
        endRow = N - 1,
        startCol = 0,
        endCol = M -1;
    while (startRow <= endRow && startCol <= endCol) {
        const outline = searchOutline(matrix, startRow, endRow, startCol, endCol);

        answer = answer.concat(outline.slice());
        
        startRow += 1;
        endRow -= 1;
        startCol += 1;
        endCol -= 1;
    }
    
    return answer;
};

 

Github: 54.js