[Leetcode] 79. Word Search

Problem

문제링크

보드판의 알파벳을 이어가면서 이용하여 word 를 만들기

Solution

DFS, Backtracking

보드판의 알파벳을 한번씩만 사용하여 인접한 알파벳을 붙어나가면서 word를 만들어내는 문제.

1. DFS 함수를 생성
2. 타겟을 만났을때 DFS 탈출 조건과 탐색 범위를 초과했을때 조건을 이용하여 가지치기한다.
   • 정답을 찾았을땐 성공 여부를 파악하였기 때문에 모든 함수 실행을 종료하도록한다.
   • 현재 길이가 word의 문자열 길이를 초과하였을때 실행을 종료한다.
   • 다음 인덱스가 보드판의 범위를 벗어나지 않도록한다.
   • 이미 한번 사용한 알파벳을 사용하지 못하도록한다.
   • word를 만드는데 필요한 알파벳인지 확인한다.
3. 사용여부의 체크는 DFS가 실행이 종료되는 시점에서 이전 depth의 함수에게 돌려줘야한다.
4. DFS의 최초 실행 조건에 word의 앞글자와 동일한지 조건을 추가하여 속도를 개선한다.

TS Code

function exist(board: string[][], word: string): boolean {
  let answer = false
  const dirs = [
    [1, 0],
    [0, 1],
    [-1, 0],
    [0, -1],
  ]
  const visited = Array.from(Array(board.length), (_, i): boolean[] => Array(board[i].length).fill(false))
  const DFS = (y: number, x: number, str: string) => {
    if (answer) return
    if (word.length < str.length) return
    if (word === str) {
      answer = true
      return
    }

    for (const [dy, dx] of dirs) {
      const ty = dy + y
      const tx = dx + x

      if (0 <= ty && ty < board.length && 0 <= tx && tx < board[ty].length) {
        if (visited[ty][tx]) continue
        const c = board[ty][tx]
        if (c !== word[str.length]) continue
        visited[ty][tx] = true
        DFS(ty, tx, str + c)
        visited[ty][tx] = false
      }
    }
  } // DFS

  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (word[0] !== board[i][j]) continue

      visited[i][j] = true
      DFS(i, j, board[i][j])
      visited[i][j] = false
    }
  }

  return answer
}