[알고리즘] Word Search

포인트

• 4가지 인접 방향 단어들을 이어가면서 타겟 언어가 있는지, 없는지를 확인하는 알고리즘 입니다. 재귀적으로 처리를 하면서 확인하는 알고리즘입니다.

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

class Solution:
    def __init__(self) -> None:
        self.flag = False
        self.dx = [0, 0, 1, -1]
        self.dy = [1, -1, 0, 0]

    def go(self, string: str, cnt: int, board: list, word: str, row: int, col: int) -> None:
        if self.flag:
            return

        if cnt == len(word):
            if string == word:
                self.flag = True
            return

        for i in range(4):
            nx = row+self.dx[i]
            ny = col+self.dy[i]

            if not (0 <= nx < len(board) and 0 <= ny < len(board[0])):
                continue
            self.go(string+board[nx][ny], cnt+1, board, word, nx, ny)

    def exist1(self, board: List[List[str]], word: str) -> bool:
        n = len(board)
        m = len(board[0])

        for row in range(n):
            for col in range(m):
                self.go(board[row][col], 1, board, word, row, col)
                if self.flag:
                    return True
        else:
            return False

처음 생각한 아이디어는 말 그대로 그냥 백트랙킹을 구현하는 것이였습니다.

최대한 성립되지 않는 조건들을 배제하고 재귀 함수를 콜 하는 방식입니다. 

여기서 저의 문제점을 발견하였습니다. 평소에는 인식을 못하고 있었는데, 
재귀 함수를 짤때, 반환 값을 생각안하고 전역으로 짠다는 것입니다. 

class Solution:         
    def dfs(self, board: list, i: int, j: int, word: str) -> bool:
        if len(word) == 0:
            return True
        if not(0 <= i < len(board) and 0 <= j < len(board[0])) or word[0] != board[i][j]:
            return False
        temp = board[i][j]
        board[i][j] = "#"  
        result = self.dfs(board, i+1, j, word[1:]) or self.dfs(board, i-1, j, word[1:]) or self.dfs(board, i, j+1, word[1:]) or self.dfs(board, i, j-1, word[1:])
        board[i][j] = temp

        return result

    def exist2(self, board: List[List[str]], word: str) -> bool:
        if not board:
            return False
        n = len(board)
        m = len(board[0])

        for row in range(n):
            for col in range(m):
                if self.dfs(board, row, col, word):
                    return True
        else:
            return False

그래서 반환 값을 받는 함수로 수정을 하였습니다. 확실히 실행 시간도 줄고 함수 자체가 깔끔해졌습니다. 
이런 부분은 확인을 하면서 작성하면 좋을 것 같습니다.