LeetCode 130 - Surrounded Regions (Medium)

문제

LeetCode - 130번

풀이 과정

X 로 둘러싸인 O 부분은 모두 뒤집었을 때 최종적으로 어떤 형태를 가진 board 가 되는지 구하는 문제입니다.
이때 한가지 주의할 점은 둘러싸는 테두리가 board 의 경계 위에 존재하면 안된다는 점입니다.

BFS 를 사용하여 문제를 해결하였으며 현재 좌표에서 상하좌우로 이동했을 때
board 를 벗어나지 않는지 체크해서 조건을 검사해줬습니다.

문제를 풀면서 발생했던 이슈 중 하나는 ES6 의 Map 자료구조와 관련된 내용입니다.
처음에는 방문 좌표를 배열 키값으로 Map 에 저장하려고 했는데 테스트해보니까
키 값으로 배열을 사용할 경우 올바르게 동작하지 않았습니다.

(만약 이렇게 하고 싶으면 배열을 다른 변수에 할당한 뒤 할당된 변수값을 활용해 키로 지정하고
has, get 등의 연산을 해야합니다.)

따라서 그냥 2차원 배열을 생성해서 visit 여부를 판단해줬습니다.

코드

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function (board) {
  if (!board.length) return board;

  const N = board.length,
    M = board[0].length;
  const visit = new Array(N).fill(null).map((row) => new Array(M).fill(0));

  function bfs(x, y) {
    let surrounded = true;
    const Q = [];
    const pos = [];
    const moves = [
      [0, 1],
      [0, -1],
      [1, 0],
      [-1, 0],
    ];

    visit[x][y] = 1;
    pos.push([x, y]);
    Q.push([x, y]);

    while (Q.length) {
      const [x, y] = Q.shift();

      for (let [dx, dy] of moves) {
        const nx = dx + x,
          ny = dy + y;

        if (nx < 0 || nx >= N || ny < 0 || ny >= M) surrounded = false;
        else {
          if (!visit[nx][ny] && board[nx][ny] === "O") {
            pos.push([nx, ny]);
            Q.push([nx, ny]);
            visit[nx][ny] = 1;
          }
        }
      }
    }

    return [pos, surrounded];
  }

  for (let x = 0; x < board.length; x++) {
    for (let y = 0; y < board[0].length; y++) {
      if (board[x][y] === "O" && !visit[x][y]) {
        const [pos, surrounded] = bfs(x, y);

        if (surrounded) {
          pos.forEach((p) => (board[p[0]][p[1]] = "X"));
        }
      }
    }
  }

  return board;
};