[Leetcode 아주 상세한 문제풀이] 79. Word Search – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 19번 문제 Remove Nth Node From End of List 다.

우선 문제를 살펴보자.

 

리트코드 19번 문제 Remove Nth Node From End of List 링크

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

Word Search - LeetCode

 

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.

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
 
Constraints:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

 

 

문제 설명

문제에 대해 간략히 살펴보자. 크기가 m * n인 매트릭스가 주어진다. 동시에 문자열이 인풋으로 주어진다. 이때 매트릭스에서 인풋으로 주어진 문자열이 존재하는지 알아보는 문제다. 이때 매트릭스 상에서 문자열이라 함은 서로 연결되어 있어야 하며 수직으로 혹은 수평으로 연결된 문자의 집합을 의미한다. 단, 같은 위치에 있는 문자열을 중복 사용할 수 없다.

문제 예시 2번을 살펴보면 우선 4 * 3 크기의 매트릭스가 주어졌다. 이 매트릭스 상에서 문자열 "SEE"가 존재하는지 확인하라는 것이다. 매트릭스 상에서 살펴볼 수 있는 것과 같이 오른쪽 아래 코너에서 S, E, E가 존재한다. 따라서 이 경우 매트릭스 상에 해당 문자열이 존재하므로 true를 리턴하면 된다. 문제를 이해하기 어렵지 않기 때문에 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 해결하기 위하여 우리는 depth-first search (DFS) 방법을 이용할 것이다.

이 방법의 주어진 매트릭스에서 해당 문자열을 찾기 위한 모든 가능성을 탐색하는 것이다.

즉, 각 cell을 탐색하며 만약 탐색하고 있는 cell이 인풋으로 주어진 문자열에 존재하는가를 확인한다.

만약 탐색하고 있는 cell이 주어진 문자열의 첫 문자와 일치한다면 그 cell을 중심으로 위/아래/좌/우를 탐색한다.

그 중에 한 곳이라도 인풋으로 주어진 문자열의 다음 문자라면 그 cell을 중심으로 다시 위/아래/좌/우를 탐색한다.

이런 방식으로 탐색을 계속하고 이 과정에서 주어진 문자열 길이까지 연속해 매칭되는 문자열을 찾는다면 그 문자열이 매트릭스에 존재하는 것이다.

우리가 DFS 방법을 이용하는 주된 이유는 backtrack을 이용할 수 있다는 점 때문이다.

예를 들어 문제 예시 1번에서 처럼 "ABCCED"라는 문자열을 찾는다고 생각해 보자.

매트릭스 상에서 DFS방식을 이용하여 ABCCE까지 찾았다고 생각해 보자.

이제 마지막에 찾은 C를 중심으로 위/아래/좌/우를 탐색해야 하는데 찾다보니 그 다음 문자인 D를 찾을 없는 경우가 있다.

이 경우 다시 앞으로 backtrack 하여 ABCC 부터 (혹은 그 이전부터) 다시 탐색을 이어나갈 수 있다.

이런 방식으로 매트릭스안에 모든 cell들을 탐색하며 주어진 문자열이 존재하는지 않는지 확인할 수 있다.

이제 코드로 한 번 살펴보자.

 

 

문제 풀이

매트릭스와 찾고자 하는 문자열을 입력받을 함수를 정의해 준다. (line 1)

만약 매트릭스가 존재하지 않는다면 탐색이 무의미 하므로 false를 리턴하고 종료한다. (line 2-3)

위에서 설명한대로 주어진 매트릭스의 가장 위 왼쪽부터 탐색을 시작한다. (line 21-22)

탐색하고 있는 cell에 대하여 DFS 함수를 불러와 탐색을 진행한다. (line 23)

이제 dfs 함수를 정의해준다. (line 5)

우선 문자열을 찾았다는 만족 조건을 설정해 주는데 문자열 길이가 현재까지 탐색한 문자 길이와 같은 경우 그 문자열을 찾은 것이므로 true를 리턴한다. (line 6-7)

만약 탐색하고 있는 곳이 매트릭스 밖으로 벗어나거나 혹은 현재 탐색하고 있는 cell의 문자가 찾고자 하는 문자열의 문자와 같지 않은 경우 false를 리턴한다. (line 8-9)

우리는 DFS를 통해 탐색을 하면 backtrack 해야 하기 때문에 현재 탐색하는 cell 까지 찾은 문자열을 저장할 변수를 하나 만들어 준다. (line 11)

그리고 이미 탐색한 cell의 경우 마크를 해준다. (line 12)

이제 탐색하고 있는 cell을 중심으로 위/아래/좌/우를 DFS 함수를 재귀적으로 불러와 탐색을 한다. (line 15-16)

이때 k+1로 표시되는 이유는 다음 문자 탐색을 하므로 문자열 길이가 하나 늘어나기 때문이다.

탐색을 마치고 나면 다시 탐색한 문자열을 임시 저장할 변수를 리셋해준다. (line 18)

이 모든 과정을 마치고 나면 found를 리턴해준다. (line 19)

다시 line 23으로 돌아와보면 DFS를 이용해 인풋으로 주어진 매트릭스에서 해당 문자열이 있는지 확인하였다.

만약 해당 문자열이 존재한다면 found가 리턴되었으므로 true가 리턴되고 종료된다. (line 24)

하지만 double for loop로 매트릭스의 모든 cell을 탐색했음에도 true가 리턴되지 않고 탐색이 종료될 경우 해당 문자열이 존재하지 않는 것이므로 false를 리턴하고 종료한다. (line 26)

 

 

문제 풀이 코드

def exist(board, word):
    if not board:
        return False
 
    def dfs(board, word, i, j, k):
        if k == len(word):
            return True
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
            return False
 
        temp = board[i][j]
        board[i][j] = "#"  # Mark as visited
 
        # Explore all adjacent cells
        found = dfs(board, word, i+1, j, k+1) or dfs(board, word, i-1, j, k+1) \
                or dfs(board, word, i, j+1, k+1) or dfs(board, word, i, j-1, k+1)
 
        board[i][j] = temp  # Reset the cell back to its original value
        return found
 
    for i in range(len(board)):
        for j in range(len(board[0])):
            if dfs(board, word, i, j, 0):
                return True
 
    return False
 
# Test the function with the provided examples
board1 = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word1 = "ABCCED"
print(exist(board1, word1))  # Output: True
 
board2 = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word2 = "SEE"
print(exist(board2, word2))  # Output: True
 
board3 = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word3 = "ABCB"
print(exist(board3, word3))  # Output: False
 

 

 

관련 문제

리트코드 48번 Rotate image 문제 풀이 (링크)

리트코드 54번 Spiral matrix 문제 풀이 (링크)

리트코드 73번 Set matrix zeroes 문제 풀이 (링크)

 

79. Word Search