[2024] day 95. Leetcode 79. Word Search

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 4월 3일 (수)
Leetcode daily problem

79. Word Search

https://leetcode.com/problems/word-search/?envType=daily-question&envId=2024-04-03

Problem

m x n 크기의 행렬과 문자열 단어가 주어질 떄, 해당 행렬의 그리드에 단어가 있으면 true를 반환한다.

단어는 순차적으로 인접한 셀의 문자로 구성될 수 있으며, 인접한 셀은 수평 또는 수직으로 이웃한다. 동일한 문자 셀은 두 번 이상 사용할 수 없다.

Solution

DFS(Depth-First Search), 깊이 우선 탐색

dfs 함수를 만들어 주어진 좌표와 단어의 인덱스를 사용한다. 현재 좌표(r,c)에서 시작해 단어의 각 문자가 현재 위치에서 인접한 셀을 통해 형성될 수 있는지를 파악한다.
단어가 형성될 수 있으면 True, 아니면 False를 반환한다.
재귀호출을 통해서 인접한 셀을 계속 탐색하고, 이미 방문한 셀을 피하기 위해서 방문한 좌표를 업데이트 한다.

Code

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        visited = set()
        
        def dfs(r,c,i):
            if i == len(word):
                return True
            if r<0 or c<0 or r>=ROWS or c>=COLS or (r,c) in visited or word[i]!=board[r][c]:
                return False
            
            visited.add((r,c))
            res = (dfs(r+1,c,i+1) or dfs(r-1,c,i+1) or dfs(r,c+1,i+1) or dfs(r,c-1,i+1))
            visited.remove((r,c))
            return res
        
        
        for r in range(ROWS):
            for c in range(COLS):
                if dfs(r,c,0):
                    return True
        return False
        

Complexicity

시간 복잡도

주어진 그리드의 모든 셀을 탐색하면서 DFS를 실행한다.
전체 시간 복잡도는 O(ROWSCOLS4^N)이다.
상화좌우 네 방향으로 이동해 4의 거듭제곱만큼의 재귀 호출이 발생한다.

공간 복잡도

재귀 호출 중에는 호출 스택이 쌓이고 추가 공간이 필요하게 된다.
방문한 셀을 업데이트하면서 사용되는 O(ROWS*COLS +N)의 공간복잡도가 발생한다.