[LeetCode]Word Search

https://leetcode.com/problems/word-search/

Word Search - LeetCode

 

문제 분석

주어진 board를 수평, 수직으로 이동하면서 탐색할 때 word를 만들 수 있는지를 구하는 문제입니다.

 

처음 시도한 답안

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        row = len(board)
        col = len(board[0])
        path = set()

        def dfs(i, j, word_idx):
            # 단어를 찾은 경우, 아래의 조건문에서 필터링 되지 않으면 단어를 찾은 것
            if word_idx == len(word):
                return True

            # Grid의 위치를 벗어나거나 or 단어가 다르거나 or 이미 방문한 포인트라면 False
            if i < 0 or j < 0 or i >= row or j >= col or word[word_idx] != board[i][j] or (i, j) in path:
                return False
                
            # 방문 경로 추가
            path.add((i,j))

            # 4방향으로 탐색하는 과정, 하나의 케이스라도 True 이면 단어를 찾은 것
            res = (
                dfs(i, j+1, word_idx+1) or
                dfs(i+1, j, word_idx+1) or
                dfs(i, j-1, word_idx+1) or
                dfs(i-1, j, word_idx+1)
            )
            
            # 방문 경로 제거
            path.remove((i, j))

            return res

        # Grid를 순회하면서 dfs 수행
        for r in range(row):
            for c in range(col):
                # 시작 글자가 word의 시작글자가 동일한 경우에만 dfs를 수행
                if board[r][c] == word[0] and dfs(r, c, 0):
                    return True

        return False

접근 방법

1. dfs를 이용해 4가지 방향으로 탐색합니다.
2. dfs 내부에서
   1. 단어를 찾은 경우라면 True를 return 합니다.
   2. 4가지 방향을 탐색하다가 Grid의 위치를 벗어난 경우 or 단어가 틀린 경우 or 이미 방문한 위치라면(중복 탐색x) False를 return 합니다.
   3. 방문한 좌표를 path(set)에 추가합니다.
   4. 4가지 방향에 대해 dfs를 재귀적으로 호출하도록 합니다. 호출한 결과중 하나라도 True 이면 단어를 찾은 것입니다.
   5. 방문한 경로를 제거합니다.
   6. 마지막으로 res를 return 합니다. 
3. Grid를 이중 순회하면서 dfs를 수행하도록 합니다.
   1. 단, 시작 글자가 word의 시작 글자와 동일한 경우에만 수행합니다.
   2. word를 발견하게 되면 True를 return 합니다.
4. 발견할 수 없다면 False를 return 합니다.

기본적으로 word를 만들어가는 과정은 DFS를 이용합니다. 다만, 4가지 방향으로 탐색하는 것과 그에 따른 여러가지 탈출 조건을 고려해내는 것이 어려웠던 문제입니다.