📌 문제 설명

Word Search 문제 보기

📌 문제 접근

이번에 코딩테스트를 하나 응시하면서, 배가 아파서 이런 부류의 문제를 못 풀어 한이 생겼다. 그래서 한 번 풀어 보았다.

단순 무식한 풀이 방법

1. 보드의 모든 칸을 시작점으로 삼아 DFS를 실행.
2. 각 칸에서 단어의 다음 문자와 일치하는지 확인.
3. 일치하면 해당 칸을 방문 표시하고, 다음 문자로 이동.
4. 더 이상 이동할 수 없거나 단어를 찾으면 백트래킹.

이건 솔직히 무호흡으로 풀 수 있는 문제인데, 너무 아쉬웠다. 좀 더 이런 문제에 익숙해져서 시간이 없을 때도 쉽게 풀 수 있도록 해야겠다.

📌 내가 작성한 코드

const exist = (board, word) => {
  const [m, n] = [board.length, board[0].length];
  const dx = [0, 0, -1, 1];
  const dy = [-1, 1, 0, 0];
  let answer = false;

  const dfs = (x, y, idx) => {
    if (answer) return;
    if (idx === word.length) {
      answer = true;
      return;
    }
    for (let l = 0; l < 4; l++) {
      const nx = x + dx[l];
      const ny = y + dy[l];
      if (0 <= nx && 0 <= ny && nx < m && ny < n) {
        if (word[idx] === board[nx][ny]) {
          const temp = board[nx][ny];
          board[nx][ny] = "*";
          dfs(nx, ny, idx + 1);
          board[nx][ny] = temp;
        }
      }
    }
  };
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (word[0] === board[i][j]) {
        const temp = board[i][j];
        board[i][j] = "*";
        dfs(i, j, 1);
        board[i][j] = temp;
      }
      if (answer) return answer;
    }
  }
  return answer;
};

📌 시간 복잡도

• M * N: 보드의 모든 칸(i, j)을 시작점으로 하여 탐색을 시도.
• 3^L: DFS 탐색의 깊이는 단어의 길이인 L까지.
  • 첫 번째 칸에서는 4방향으로 뻗어나갈 수 있지만, 두 번째 칸부터는 직전에 왔던 길(방문 처리된 칸)로 되돌아가지 않으므로 실제 선택지는 최대 3개로 제한.
  • 따라서 각 시작점당 최악의 경우 3^L번의 연산이 수행.
• 결론: 이론적인 상한선은 O(M * N * 4^L)로 표기하기도 하지만, 실제 탐색 경로를 고려한 더 정확한 복잡도는 O(M * N * 3^L).

📌 참고 링크

• 재귀 함수와 깊이 우선 탐색(DFS)
• 백트래킹 알고리즘