79. Word Search

Word Search - LeetCode

영어 대문자로 구성된 2차원 배열이 주어진다.

임의의 위치에서 시작해 네 방향으로 이동하면서 주어진 문자열을 만들 수 있는지를 판단하는 문제다.

 

예시

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

여기서 방문한 격자를 중복해서 선택할 순 없다. 그러므로 위 예시에선 "ASA"는 true 지만 "ASAA"는 false를 반환해야 한다.

 

1. DFS

from typing import *


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

        height, width = len(board), len(board[0])
        x, y = [0, 0, 1, -1], [1, -1, 0, 0]
        visited = [[0] * width for _ in range(height)]
        flag = False

        def dfs(cur_x, cur_y, cur_index):
            nonlocal flag
            if flag:
                return
            visited[cur_x][cur_y] = 1

            if cur_index == len(word) - 1:
                flag = True
                return

            for i in range(4):
                new_x, new_y = cur_x + x[i], cur_y + y[i]
                if 0 <= new_x < height and 0 <= new_y < width:
                    if not visited[new_x][new_y] and board[new_x][new_y] == word[cur_index + 1]:
                        dfs(new_x, new_y, cur_index + 1)

            visited[cur_x][cur_y] = 0

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

2차원 배열에 대한 DFS를 구현하면 해결할 수 있다.

 

최 하단의 2중 반복문이 main인데, board [i][j]가 word의 첫 문자와 같다면 탐색을 시작할 수 있는 지점이기 때문에 이 지점부터 DFS를 시도한다. DFS 함수에선 좌표와 word의 index값을 넣어서 현재 좌표의 4방을 보고 만일 word [index+1] 값과 같다면 해당 방향으로 DFS를 타 도록 구현했다.

 

DFS이기 때문에 방문 처리를 원복 해주어야 다음 재귀에서도 탐색할 수 있기 때문에 재귀 함수 마지막엔 방문 처리를 해제해주었다. 이런 식의 재귀 함수 구조는 함수가 끝나면 visited 배열도 원복 되어 따로 초기화를 해주지 않아도 된다는 장점이 있다.