[LeetCode 풀이/python] 79. Word Search (medium)

문제 설명: m x n 형태의 격자판 board 와 단어 word 가 주어졌을 때, 해당 격자판에 단어 word 가 존재하는지를 찾으시오. 단어 word 는 연속적으로 인접한 셀의 문자들로 구성될 수 있으며, 이 때 '인접한' 셀들은 수평 혹은 수직 방향으로 이웃한 것들이다. 동일한 문자 셀은 한 번을 초과하여 사용될 수 없다.

 

(Given an m x n board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where "adjacent" cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.)

 

예시 1)

입력: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"  -->  출력: true

 

예시 2)

입력: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" -->  출력: true

 

예시 3)

입력: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"  -->  출력: false

 

제한 조건:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 200
• 1 <= word.length <= 10^3
• board 와 word 는 오로지 영문 대소문자로만 이루어져 있다

------ * ------ * ------ * ------

 

[풀이 1안]  --  w/solution peeping

• 접근법
  • 백트래킹을 이용하여 풀이하는 접근법은 파악했으나 구체적인 구현 과정에서 난항을 겪고 (...) Discussion 을 참고함
  • 격자판 board 의 각 셀이 백트래킹 탐색의 시작점이 될 수 있으므로, 각 셀 (i, j) 에 대해 DFS 알고리즘을 적용
  • Recursively 적용되는 DFS 함수의 경우,
    • 찾고자 하는 단어 word 의 맨 앞 문자부터 차례로 확인하며 탐색을 진행할 수록 탐색 범위(단어 길이) 를 줄임
    • 1) 인접한 셀에 찾는 문자가 존재하여 탐색을 계속 진행할 수 있는 경우, 또는
    • 2) 탐색 끝에 찾고자 하는 단어 word 를 구성하는 문자를 다 찾았을 경우 True 를 리턴하며 탐색을 종료해 나감
      (문자를 다 찾고 Recursively True > True > ... > True 의 끝에 최종적인 출력이 True 로 나오게 되는 것!)
    • 3) 한편, 탐색 진행 과정에서 격자판을 벗어난 범위로 셀을 가리키게 되거나, 셀의 문자가 찾는 문자가 아닌 경우는 False 를 리턴하며 가지치기를 수행
  • 이 때, 각 셀의 문자는 단어 구성 과정에서 최대 한 번씩만 사용될 수 있으므로, 현재보다 앞 자리에서 등장하는 문자를 만드는 데에 사용된 문자 셀은 탐색 범위에서 제외해야 함!
    • 직전에 사용된 문자 셀을 '#' 등의 inavailable 한 문자로 대체하여 (잠시 가려놓는 식...) 탐색 범위에서 제외시킴**
  • 인접한 셀에 찾고자 하는 다음 문자가 존재하는지 확인하기 위해 해당하는 상/하/좌/우 셀에 대해 DFS 함수를 적용하되, 이들을 OR 로 연결한 결과를 변수 res 로 받아** 어느 한 방향으로라도 이동 가능하면 True 를 리턴하고 계속 탐색을 진행할 수 있게 함 

 

• 코드 구현

def exist(board: List[List[str]], word: str) -> bool:
    res, visited = [], set()
    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(board, i, j, word, res):
                return True
    return False
    
def dfs(board, i, j, word, res):
    if len(word) == 0:
        return True
        
    if (i < 0) or (i >= len(board)) or (j < 0) or (j >= len(board[0])) \
        or (board[i][j] != word[0]):
        return False

    board[i][j] = '#'
    res = self.dfs(board, i-1, j, word[1:], res) or self.dfs(board, i+1, j, word[1:], res) or \
          self.dfs(board, i, j-1, word[1:], res) or self.dfs(board, i, j+1, word[1:], res)
    board[i][j] = word[0]
    return res

 

• 결과
  • 백트래킹을 포함한 recursive 접근법들은 Complexity 계산이 어려워... ㅜ_ㅜ
  • 격자판의 각 셀을 시작점으로 하여 word 길이만큼 확인을 위해 매번 사방으로 확인을 하니... len(word) = k 라 할 때, O(m * n * 4^k) 인 것으로 생각됨
  • 백트래킹의 핵심인 DFS 알고리즘 구현에 있어서 정교하게 케이스를 나누고 구조화 하는 것이 중요하구나 싶음... ㅠ_ㅠ