문제

• m*n grid board
• string word
• board에 word 있으면 true, 없으면 false

풀이

• dfs로 시작글자 발견 -> 다음글자 -> 다음글자
• stack으로 풀었다가, visited track이 복잡할 것 같아서 recursion으로 해결

from copy import copy

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        global isExist
        rowN = len(board)
        colN = len(board[0])
        wordLen = len(word)

        possibleStart = []
        for row, li in enumerate(board):
            for col, el in enumerate(li):
                if el == word[0]:
                    possibleStart.append([row, col])

        for startR, startC in possibleStart:
            visited = set()
            visited.add((startR, startC))
            if wordLen == 1:
                return True
            else:
                isExist = False
                dfs(board, word, 0, startR, startC, visited, rowN, colN, wordLen)
            if isExist:
                return True
        return False


def dfs(board, word, count, r, c, visited, rowN, colN, wordLen):
    global isExist
    count += 1
    if count < wordLen:
        for k in range(4):
            newR = r + dx[k]
            newC = c + dy[k]
            if 0<=newR<rowN and 0<=newC<colN and (newR, newC) not in visited and board[newR][newC] == word[count]:
                if count+1 == wordLen:
                    isExist = True # flag
                    return
                newV = copy(visited)
                newV.add((newR,newC))
                dfs(board, word, count, newR, newC, newV, rowN, colN, wordLen)

결과