LeetCode 79(Word Search, Python)

1. 문제 링크

• Word Search - LeetCode

Word Search - LeetCode

2. 문제 설명

• board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]] 처럼 보드가 이중 리스트로 주어지고 찾아야하는 단어가 word = "ABCCED”로 주어질 때, 한 줄로 이어서 단어를 완성할 수 있으면 True, 아니면 False 반환

3. 처음 풀이

• 너무 느려서 어쩔 때는 pass 어쩔 때는 Time Limit Exceeded

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        pathWord = ''  # 현재까지 찾은 문자열을 저장하는 변수

        def recur(board, word, pathWord, pathIndex, position):
            y, x = position[0], position[1]
            
            if pathWord == word:  # 현재까지 찾은 문자열이 주어진 단어와 일치하면 True 반환
                return True
            else:
                curWord = word[len(pathWord)]  # 현재 찾아야 할 문자

            # 현재 위치가 유효한 범위인지 확인
            if x < 0 or x >= len(board[0]) or y < 0 or y >= len(board):
                pass
            # 이미 방문한 위치인지 확인
            elif [y, x] in pathIndex:
                pass
            # 현재 위치의 문자가 찾아야 할 문자와 일치하는지 확인
            elif board[y][x] == curWord:
                pathWord += curWord  # 현재 문자를 pathWord에 추가
                pathIndex += [position]  # 현재 위치를 방문한 위치에 추가
                # 상하좌우로 다음 위치를 확인하기 위해 재귀 호출
                for nextPosition in [[y+1, x], [y, x+1], [y-1, x], [y, x-1]]:
                    if recur(board, word, pathWord, pathIndex, nextPosition):
                        return True
                pathWord = pathWord[:-1]  # 재귀에서 돌아오면서 현재 문자를 제거
                pathIndex.pop()  # 재귀에서 돌아오면서 현재 위치를 방문한 위치에서 제거

        # 모든 시작점에 대해 검사
        for row in range(len(board)):
            for col in range(len(board[0])):
                if recur(board, word, pathWord, [], [row, col]):
                    return True
        
        return False  # 모든 시작점에서도 찾지 못했으면 False 반환

4. 다른 풀이

• 로직은 같으나 훨씬 빠르다.
• 처음 풀이의 코드가 느린 이유로 짐작되는 점들
  • 현재 위치 기준으로 4방향으로 재귀를 실행 시킨 후, 재귀함수 안에서 유망한 케이스인 지 아닌 지를 따진다. 이러면 불필요한 재귀 실행이 많다. 미리 유망한 방향을 따져서 그 방향으로만 재귀를 실행시키는 것이 유리.
  • 문자열 pathWord를 계속 조작하는데 파이썬에서 문자열은 불변 객체로 새로운 메모리 비용이 계속 발생함. 문자열 대신 리스트 쓰는 것이 유리.
    • 아래 풀이에서는 pathWord를 사용할 필요 없이 지나온 칸의 개수만 기록하였음.
  • path를 리스트로 관리했는데 in, not in 판별을 계속해야하므로 리스트보다 set이 유리.
    • 아래 풀이에서는 이미 지나온 칸을 리스트나 set에 보관하지 않고 현재 칸을 잠시 ‘/’로 바꾼 후 재귀 실행 후 다시 원래 값으로 바꾸는 기법을 통해 이미 탐색한 칸을 다시 탐색하지 않도록 하였음.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i: int, j: int, k: int) -> bool:
            if k == len(word):
                return True
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
                return False
            temp, board[i][j] = board[i][j], '/'
            res = dfs(i+1, j, k+1) or dfs(i-1, j, k+1) or dfs(i, j+1, k+1) or dfs(i, j-1, k+1)
            board[i][j] = temp
            return res
        
        m, n = len(board), len(board[0])
        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

5. 배운 점

• 문제를 푸는 논리는 간단한데 문법적으로 헷갈린 부분이 있다.
  • 재귀함수에서 return True를 했을 때 전체 함수에서 어떨 때는 True가 나오고 어떨 때는 False가 나왔다. 헷갈려서 시도해본 6가지 케이스.
  • 헷갈린 점을 한마디로 정리하면 명시적인 return이 없을 때 None이 전달된다는 것에 유의하자.
• 아, 그리고 처음 풀이에서 불필요하게 많은 변수를 함수 인자로 전달하였다. 바깥에 상수로 빼는게 나을 듯.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        def recur(board, word):
            if len(word) == 0:
                return True
            recur(board, word[1:])
        recur(board, word)

    #result: False
		#recur(board, word[1:])가 True 또는 False를 반환하지 않고, 함수 호출 후에 아무런 처리도 하지 않아서 항상 None이 반환되므로 결과는 False

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        def recur(board, word):
            return True
				recur(board, word)

    #result: False
		#exist 함수 입장에서 return이 없다. recur(board, word)가 True 이지만 이를 exist함수가 return하지 않음. return이 없으므로 그냥 None. 따라서 Flase

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        def recur(board, word):
            return True
				if recur(board, word) == True:
						return True
		
    #result: True

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        def recur(board, word):
            return True
				return recur(board, word)
		
    #result: True

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        def recur(board, word):
            if len(word) == 0:
								return True
						recur(board, word[1:])
				return recur(board, word)
		
    #result: False
		#recur(board, word[1:])이 True여도 앞에 명시적인 return이 없어서 None에 전달되어 False

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        
        def recur(board, word):
            if len(word) == 0:
								return True
						return recur(board, word[1:])
				return recur(board, word)
		
    #result: True