[Leetcode/파이썬] 79. Word Search

Word Search

---

Given an m x n grid of characters board and a string word, return true if 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.

 

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

 

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

 

Follow up: Could you use search pruning to make your solution faster with a larger board?

 

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        for i in range(len(board)) :
            for j in range(len(board[0])) :
                if self.dfs(i, j, 0, board, word) :
                    return True
        
        return False
        
    def dfs(self, i: int, j: int, k: int, board: List[List[str]], word: str) :
        if not (0 <= i < len(board) and 0 <= j < len(board[0])) :
            return False

        if board[i][j] != word[k] :
            return False
        
        if k == len(word) - 1 :
            return True

        tmp = board[i][j]
        board[i][j] = "#"

        for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)) :
            ni, nj = i + di, j + dj

            if self.dfs(ni, nj, k + 1, board, word) :
                return True

        board[i][j] = tmp
        return False

처음에는 BFS로 풀이를 시작했다. 그러나 이게 아니라 한줄긋기 처럼 지나온 곳은 다시 돌아가지 못하는 수 때문에 오답을 냈었다. 쉽게 생각하자. 이 문제는 한 줄 긋기 문제이다. 그렇기 때문에 BFS가 아니라 백트래킹을 활용하여 문제를 해결해야 한다. 

• DFS: i, j 좌표, k 글자 위치(word의 인덱스와 대치), borad, word
  • 범위내, 네방향, 미방문, 정확한 방문 4조건이 부합하는지 체크
  • 1번 if = 범위 내인지.
  • 2번 if = 정확한 방문인지
  • 3번 if = 종료 조건
  • tmp = board[i][j](현재 위치) 따로 저장
  • 현재 위치 = "#"은 방문처리
  • 네 방향으로 방문하면서 재귀로 처리. 
  • 부합하는 바가 없으면 현재 위치를 다시 원상복구 => 이 방법은 틀렸으니 나가자.
• 본 함수 
  • 전체를 돌아가면서 현재의 위치가 첫번째 단어(word[0]) 인지 체크. => dfs(i, j, k=0)
  • 하나라도 True가 나오면 return True 로 반환
  • 마지막 수 까지 True가 나오지 않았다면 False 반환

처음 BFS로 풀어보고 아 뭔가 이상함을 느꼈지만 테스트케이스는 다 통과하니 괜찮겠지? 했지만 역시나였다. 한줄긋기 문제이기 때문에 DFS가 적합하며 백트래킹까지 접목해야 했던 문제였다. 재귀 함수는 조건을 저렇게 다 앞에 빼놓고 하는 게 더 낫구나. DFS나 백트래킹 더 연습을 해야겠다.