[LeetCode] 79. Word Search (Daily Question)

문제

---

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.

 

영문자로 구성된 보드와 단어가 주어졌을 때, 단어가 보드에 있는지 판별하는 문제이다.

문자끼리는 가로 및 세로로 연결되어 있어야 한다.  

 

에를 들면,

board는 [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], 

word는 "ABCCED" 가 주어졌을 때

왼쪽 그림과 같은 형태로 단어가 존재하므로 True를 반환한다.

 

---

 

풀이

아이디어

DFS를 사용한다.

보드의 최대 크기는 6*6으로 한 칸 한 칸 탐색하며 문자가 만들어지는지 판별해도 괜찮을 듯 하다.

 

코드

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

        # 탐색하는 함수
        # pos: 현재 칸 위치, searched: 단어를 만들기 위해 탐색한 경로
        def search(pos, searched):
            
            # 현재 탐색중인 word의 문자 차례
            ln = len(searched)+1

            # 주어진 문자열이 완성된 경우
            if ln == len(word): return True

            x, y = pos
            searched.append(pos)
            
            # 주변 칸에 다음 문자가 있는지 확인 후 재귀
            if (x-1, y) not in searched and x-1 >= 0 and board[x-1][y] == word[ln]:
                # 리스트를 복사하려면 .copy()를 해줘야 함
                # 안하면 함수 내에서 값을 바꿨을 때 외부에 영향을 미침
                if search((x-1, y), searched.copy()): return True

            if (x+1, y) not in searched and x+1 < len(board) and board[x+1][y] == word[ln]:
                if search((x+1, y), searched.copy()): return True

            if (x, y-1) not in searched and y-1 >= 0 and board[x][y-1] == word[ln]:
                if search((x, y-1), searched.copy()): return True

            if (x, y+1) not in searched and y+1 < len(board[0]) and board[x][y+1] == word[ln]:
                if search((x, y+1), searched.copy()): return True

            return False

        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] == word[0] and search((i, j), []): 
                    return True

        return False

---

 

후기

---

난이도

탐색알고리즘에 익숙해져 있기 때문에 어렵지는 않았다.

단어를 만들기 위해 탐색했던 경로는 다음 경로에서 제외해주어야 한다는 예외사항이 있었지만,그 외에는 따로 없어서 까다롭지는 않았다.

 

주의해야할 사항으로는 함수의 인자값으로 리스트를 넣을 때, .copy()를 통해 복사된 상태로 넣어주어야 한다는 것이다.

그냥 전달하면 함수 내부에서 리스트의 요소를 변경했을 때 외부까지 반영이 된다.

 

다른 풀이

BFS를 사용해 단어가 될 수 있는 후보들만 남기고 계속 탈락시키는 방식도 가능할 듯 싶다.