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

 

 

 

m x n의 배열이 주어지고 단어가 string으로 주어진다면 그 단어가 보드 배열에 있는지 확인하는 문제

상하좌우로 움직일 수 있고 이미 방문한 칸은 재방문이 불가능하다

 

 

 

https://leetcode.com/problems/word-search/description/

 

 

 

---

 

 

 

 

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

 

 

 

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

 

 

 

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

 

 

 

---

 

 

 

 

이런 문제가 나오면 자연스럽게 백트래킹, DFS 사용하면 되겠구나 생각한다

 

체크해야될 부분:

1. 현재 확인하는 칸이 보드에 유효한 칸인지

2. 이미 방문한 칸인지

3. 확인하는 칸이 알맞는 단어의 순서에 있는 값인지

 

이런 점을 유의하면서 코드를 작성했다

 

 

 

 

백준, 프로그래머스에서는 이런 문제를 이런식으로 구현한다:

class Solution:
    def exist(self, board, word):
        dx = [0, 0, 1, -1]
        dy = [1, -1, 0, 0]

        def dfs(x, y, index):
            if index == len(word):
                return True
            
            visited[x][y] = True
            for i in range(4):
                ux, uy = dx[i] + x, dy[i] + y
                if (0 <= ux < row and 0 <= uy < col and 
                    not visited[ux][uy] and 
                    board[ux][uy] == word[index]):
                    if dfs(ux, uy, index + 1):
                        return True
            visited[x][y] = False
            return False
        
        row, col = len(board), len(board[0])
        visited = [[False for _ in range(col)] for _ in range(row)]
        for i in range(row):
            for j in range(col):
                if board[i][j] == word[0] and dfs(i, j, 1):
                    return True
        return False

 

 

 

---

 

 

 

반면 Leetcode 또는 북미쪽의 코딩은 이런식으로 구현 스타일을 가져간다:

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

        def dfs(x, y, index):
            if index == len(word):
                return True
            
            if not 0 <= x < row or not 0 <= y < col: return False
            if (x, y) in visited: return False
            if board[x][y] != word[index]: return False
            
            visited.add((x, y))
            check = (
                dfs(x + 1, y, index + 1) or
                dfs(x - 1, y, index + 1) or
                dfs(x, y + 1, index + 1) or
                dfs(x, y - 1, index + 1)
            )
            visited.remove((x, y))
            
            return check

        for i in range(row):
            for j in range(col):
                if board[i][j] == word[0]:
                    if dfs(i, j, 0):
                        return True
        
        return False

 

 

 

 

둘다 참고하고 더 편한 방식을 익혀서 상황마다 사용하는게 좋을것 같다

 

 

 

둘다 비슷한 결과를 보여준다