LeetCode 79 - Word Search (Medium)

문제

LeetCode - 79번

풀이 과정

이차원 배열에서 인접한 문자들을 이용해서 특정 단어를 만들 수 있는지 판단하는 문제입니다.

백트래킹 을 활용해서 문자가 일치하지 않으면 다음 위치를 찾도록 탐색을 하면 됩니다.
또한 원하는 단어를 찾으면 다른 문자들은 탐색하지 않고 바로 true 를 반환하도록 하였습니다.

코드

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const dx = [0, 0, 1, -1];
  const dy = [1, -1, 0, 0];

  function dfs(x, y, depth, visit) {
    if (board[x][y] !== word[depth]) return false;
    else if (depth === word.length - 1) return true;

    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i],
        ny = y + dy[i];

      if (0 <= nx && nx < board.length && 0 <= ny && ny < board[0].length) {
        if (!visit[nx][ny]) {
          visit[nx][ny] = 1;
          if (dfs(nx, ny, depth + 1, visit)) return true;
          visit[nx][ny] = 0;
        }
      }
    }

    return false;
  }

  for (let x = 0; x < board.length; x++) {
    for (let y = 0; y < board[0].length; y++) {
      if (board[x][y] === word[0]) {
        const visit = new Array(board.length)
          .fill(0)
          .map((_) => new Array(board[0].length).fill(0));

        visit[x][y] = 1;
        if (dfs(x, y, 0, visit)) return true;
        visit[x][y] = 0;
      }
    }
  }

  return false;
};