[Leetcode/Python] 79. Word Search

문제 링크

Word Search - LeetCode

 

문제 설명

m x n의 문자칸과 단어가 주어지고, 단어가 문자칸에 있으면 true를 반환합니다.

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

 그림과 같이 문자칸내에서 연속해서 연결했을때, 단어가 존재하면 true, 아닐경우 false를 반환하면 된다.

 

 2차원 배열을 써야 하는 걸 보면 알다시피 DFS 관련된 알고리즘을 써야한다.

 

제한 사항

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• 문자칸과 단어는 오로지 대문자거나 소문자로만 이루어져 있다.

 

문제 풀이

 이차원 배열을 썼으므로 대체로 DFS가 쓰이는 문제다. 그래서 DFS 알고리즘중 백트레킹을 통해 문제를 해결했다.

 

 처음에는 방문기록만을 남겨서 문제를 해결했는데, 한가지 문제가 생겼다. 문자칸이 전부 A로 되어있고, 'AAAAAAAB'와 같은 단어를 찾을 때 타임아웃이 발생한다는 점이다. 다음과 같은 경우 말이다.

[["A","A","A","A","A","A"], ["A","A","A","A","A","A"], ["A","A","A","A","A","A"], ["A","A","A","A","A","A"], ["A","A","A","A","A","A"], ["A","A","A","A","A","A"]]

"AAAAAAAAAAAAABB"

 

그래서 이 경우를 따로 세는 코드를 추가하였다. 결국 문제가 풀리긴 했지만, 더 좋은 방법이 있을까 찾아보았다. 그 중 이 글에서 word를 거꾸로 하는 게 더 좋을 경우가 있다는 점을 찾았다. 

 

소스코드

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        if len(word) > m * n: return False

        # 보드의 각 알파벳의 전체 갯수와 word의 알파벳 전체 갯수를 비교
        countB = Counter()
        for i in range(m):
            for j in range(n):
                countB[board[i][j]] += 1
        countW = Counter(word)
        for key in countW.keys():
            if countW[key] > countB[key]:
                return False

        visit = [[0 for _ in range(n)] for _ in range(m)]
        def backtracking(x: int, y: int, idx: int):
            if idx == len(word):
                return True
            if 0 <= x < m and 0 <= y < n:
                if board[x][y] == word[idx] and visit[x][y] == 0:
                    visit[x][y] = 1
                    for nx, ny in direction:
                        a, b = x + nx, y + ny
                        if DFS(a, b, idx + 1):
                            return True
                    visit[x][y] = 0
            return False

        for i in range(m):
            for j in range(n):
                if backtracking(i, j, 0):
                    return True
    
        return False

 

 

코딩 테스트, 어떻게 대비해야 할까?