LeetCode 54 - Spiral Matrix (Medium)

문제

LeetCode - 54번

풀이 과정

2차원 배열 을 이용한 구현 문제입니다.
배열의 움직임에서 규칙을 찾아 화전하는 시뮬레이션을 할 수도 있지만 좀 더 간단한 방법으로
DFS 를 활용하여 모든 위치를 탐색할 수 있습니다.

시작지점 (0, 0) 에서부터 오른쪽, 아래쪽, 왼쪽, 위쪽 순서대로 방향을 틀어가며 탐색합니다.
이때 방향을 전환하는 시점은 배열을 벗어나거나 이미 방문한 지점을 다시 방문하려고 할 때입니다.

이를 활용하면 다음과 같은 코드로 원하는 연산을 수행할 수 있습니다.

코드

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  const dx = [0, 1, 0, -1];
  const dy = [1, 0, -1, 0];
  const answer = [];
  const visit = Array.from(Array(m), () => Array(n).fill(false));

  function inRange(x, y) {
    return 0 <= x && x < m && 0 <= y && y < n;
  }

  function dfs(x, y, dir) {
    if (!inRange(x, y) || visit[x][y]) return;

    visit[x][y] = true;
    answer.push(matrix[x][y]);

    let nx = x + dx[dir];
    let ny = y + dy[dir];

    if (inRange(nx, ny) && !visit[nx][ny]) {
      dfs(nx, ny, dir);
    } else {
      dir = (dir + 1) % 4;
      nx = x + dx[dir];
      ny = y + dy[dir];

      dfs(nx, ny, dir);
    }
  }

  dfs(0, 0, 0);

  return answer;
};