[LeetCode 해석 및 풀이] 79. Word Search(단어 검색)

LeetCode 문제 해석 및 풀이 방법

문제 79. 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.

 

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

 

한글

문자 board 와 문자열 word 구성된 mxn 그리드가 주어졌을 때, 그리드에 word가있으면 true를 반환합니다.

 

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

 

후속 답변: 더 큰 board 로 솔루션을 더 빠르게 만들기 위해 검색 정리를 사용할 수 있나요?

 

제한조건

• 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.

 

입출력 예

입력	출력
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"	true
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"	true
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"	false

 

해답 및 해설

파이썬 (Python)

첫번째 풀이

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        x_len = len(board[0])
        y_len = len(board)
        visited = [[False]*x_len for _ in range(y_len)]

        def check(visited, x, y, word):
            if board[y][x] != word[0]:
                return False
            
            if len(word) == 1:
                return True
            
            new_visited = [l.copy() for l in visited]
            new_visited[y][x] = True
            new_word = word[1:]

            left = (x-1 >= 0) and (not visited[y][x-1]) and (check(new_visited, x-1, y, new_word))
            right = (x+1 < x_len) and (not visited[y][x+1]) and (check(new_visited, x+1, y, new_word))
            up = (y-1 >= 0) and (not visited[y-1][x]) and (check(new_visited, x, y-1, new_word))
            down = (y+1 < y_len) and (not visited[y+1][x]) and (check(new_visited, x, y+1, new_word))

            return left or right or up or down

        for x in range(x_len):
            for y in range(y_len):
                if check(visited, x, y, word):
                    return True
        
        return False

모든 경우의 수를 다 한번씩 살펴보고 있으면 True, 없으면 False를 반환. 단어를 찾을 때 이전에 방문했던 곳은 visited에 표기하여 방문한 곳을 다시 방문하지 않도록 한다. 해당 코드는 풀이시 5062ms가 걸렸다.

 

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        x_len = len(board[0])
        y_len = len(board)
        visited = 0

        def check(visited, x, y, word):
            if board[y][x] != word[0]:
                return False
            
            if len(word) == 1:
                return True
            
            new_visited = visited | (1<<(y*x_len + x))
            new_word = word[1:]

            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

            for off_x, off_y in directions:
                new_x, new_y = x + off_x, y + off_y

                if 0 <= new_x < x_len and 0 <= new_y < y_len:
                    if not (new_visited & (1 << (new_y * x_len + new_x))):
                        if check(new_visited, new_x, new_y, new_word):
                            return True
                
            return False

        for x in range(x_len):
            for y in range(y_len):
                if check(visited, x, y, word):
                    return True
        
        return False

 방식을 비트마스크로 바꾸고 리팩토링한 코드. 비트마스크로 바꾸니 시간이 0.5초 늘고(5522ms), 처음에 해당 방향마다 체크하는  함수들을 다 나누는 식으로 리팩토링을 하니 시간초과가 떠버렸었다. GPT에게 물어보니 함수 호출이 파이썬에서는 느린 연산이라 오버헤드가 일어나는 것 같다고 했었다. 그래서 반복문 형식으로 바꾸니 확실히 기존 시간보다 짧아졌었다. (4739ms)

 

비트마스크가 느린 이유는 아마 리스트 내에 같은 자료형만 들어있을 경우 자동으로 파이썬이 최적화해서 그런거 아닐까 싶다. 비트마스크가 이론상으로 빠르다고는 하는데, 파이썬에서 비트마스크를 쓰면서 한번도 빨랐던 적이 없었다...
https://eprj453.github.io/python/2020/12/05/Python-%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%97%90%EC%84%9C-%EB%A9%94%EB%AA%A8%EB%A6%AC-%ED%95%A0%EB%8B%B9%EC%97%90-%EB%8C%80%ED%95%9C-%EC%83%9D%EA%B0%81/

[Python] 리스트에서 메모리 할당에 대한 생각

 

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        x_len = len(board[0])
        y_len = len(board)
        visited = [[False]*x_len for _ in range(y_len)]

        def check(x, y, word):
            if board[y][x] != word[0]:
                return False
            
            if len(word) == 1:
                return True
            
            visited[y][x] = True
            new_word = word[1:]

            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

            for off_x, off_y in directions:
                new_x, new_y = x + off_x, y + off_y

                if 0 <= new_x < x_len and 0 <= new_y < y_len and not visited[new_y][new_x]:
                    if check(new_x, new_y, new_word):
                        return True

            visited[y][x] = False
            return False

        for y in range(y_len):
            for x in range(x_len):
                if check(x, y, word):
                    return True
        
        return False

GPT한테 왜 비트마스크가 느리냐 물어보니까 다음과 같이 재귀적 상태 관리를 해주는 코드를 뽑아줬다. 해당 코드는 이전 코드보다 1.5초 더 빨라서 가장 빠른 코드가 되었다. (3589ms) 메모리 사용도 우수했다.(16.48MB)  

 

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        x_len = len(board[0])
        y_len = len(board)
        visited = 0

        def check(x, y, word):
            nonlocal visited

            if board[y][x] != word[0]:
                return False
            
            if len(word) == 1:
                return True
            
            visited |= (1<<(y*x_len + x))
            new_word = word[1:]

            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

            for off_x, off_y in directions:
                new_x, new_y = x + off_x, y + off_y

                if 0 <= new_x < x_len and 0 <= new_y < y_len and not (visited & (1 << (new_y * x_len + new_x))):
                    if check(new_x, new_y, new_word):
                        return True

            visited ^= (1<<(y*x_len + x))
            
            return False

        for y in range(y_len):
            for x in range(x_len):
                if check(x, y, word):
                    return True
        
        return False

재귀적 상태 관리를 비트마스크 방식으로 하니까 메모리 사용은 더 우수해졌지만(16.34MB),  시간 소요는 더 길어졌다. (4994ms) 아니 왜 비트마스크가 더 느리는데... 걍 파이썬이 최적화 해줄꺼니 깝치지 말고 리스트 쓰는게 맞는거 같다.