Leetcode 79. Word Search - Python (cf. 백준 15705)

from LeetCode79

 

Leetcode 79 문제 보기

 

문제 이해하기

m x n grid 한 칸(cell) 당 대소문자 알파벳이 한 글자씩 들어가있다.

이 때, 주어진 word를 grid에서 찾을 수 있다면 true, 찾을 수 없다면 false를 return한다.

 

탐색 규칙은 다음과 같다.

수직, 수평으로 탐색을 하되 중간에 방향을 틀 수도 있다.

또한 한 번 방문한 cell은 재방문할 수 없다.

 

아이디어 구상

손으로 문제를 푼다면 본 문제를 어떻게 풀 수 있을까?

1. 우선 하나의 cell을 찍고 이 cell이 주어진 word의 첫 글자와 일치하는지 비교한다.
2. 그리고 주어진 탐색 규칙에 맞게 탐색하며 과연 word가 존재할지 알아본다.
3. 만약 word를 발견했다면 true를 return하고 탐색을 종료, 발견하지 못했다면 다음 cell로 넘어가 1~3과정을 반복한다.

즉 Brute Force하게 풀되, 조건에 맞지 않을 경우 다음 탐색을 진행하도록 Backtracking을 하는 방식으로 해결책을 생각해보자.

 

이 때의 시간복잡도는 어떻게 될까?

우선 m x n의 grid를 순차탐색해야하므로 O(n * m),

여기에 각 cell에서 dfs를 진행해야하기 때문에 O(n * m * dfs)가 걸릴 것이다.

O(dfs)의 경우 상하좌우 4방향 중 이미 방문한 방향을 제외한다면 대략 3^len(word) 정도의 복잡도를 지닐 것이다.

즉, Time Complexity ~ O(n * m * 3^len(word)) 가 예상된다.

 

다만 cell 값이 word의 첫 글자와 일치할 때만 탐색을 시작하는 등의 Backtracking을 통해 실제 시간복잡도는 이보다는 나을 것으로 생각된다.

 

풀이

문제 풀이를 위해 필요한 도구(변수, 함수 등)들을 생각해보자.

우선 전체 grid의 크기를 rows와 cols에 담자.

또한 이미 방문한 cell을 재방문하지 않도록 방문한 cell의 좌표를 set에 넣어 보관하자.

rows, cols = len(board), len(board[0])
path = set()

 

2차원 grid의 각 cell들을 검사하며 주어진 word의 첫 글자와 일치할 때 탐색을 진행한다.

탐색 결과 word를 grid안에서 발견했다면 true를 return하고 그렇지 못했다면 false를 return한다.

for r in range(rows):
    for c in range(cols):
        if board[r][c] == word[0]:
            # search algorithm
            # if find: return True
return False

 

탐색 방법으로는 여러가지가 있을 것이다.

대표적으로 반복문을 통해 구현할수도 있고, dfs()를 통해 재귀적으로 구현할수도 있겠다.

좀 더 깔끔하고 가독성 높은 코드는 아무래도 재귀적 방식일 것이며, 여기서도 dfs()로 탐색을 진행해보자.

 

base case는 다음과 같다.

만약 word를 찾았다면 true를 return하고

현재 좌표가 grid를 벗어나거나, 값이 word와 다르거나, 이미 방문한 cell에 위치한다면 false를 return한다.

 

재귀 부분은 다음과 같다.

상하좌우를 재귀적으로 탐색할 것이며, 재귀가 종료되면 path에서 방문 좌표를 제거하여 다음 cell에서부터 시작한 탐색 시 지장이 없게 한다.

def dfs(r, c, i):
    if i == len(word):
        return True
    if (r < 0 or c < 0 or r >= rows or c >= cols or
        word[i] != board[r][c] or
        (r, c) in path):
        return False

    path.add((r, c))
    res = (dfs(r + 1, c, i + 1) or
           dfs(r - 1, c, i + 1) or
           dfs(r, c + 1, i + 1) or
           dfs(r, c - 1, i + 1))

    path.remove((r, c))
    return res

 

전체 코드는 다음과 같다.

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows, cols = len(board), len(board[0])
        path = set() # to make sure not to revisit the previous path
        
        def dfs(r, c, i): # (current r, current c, current character)
            if i == len(word):
                return True
            if (r < 0 or c < 0 or r >= rows or c >= cols or
                word[i] != board[r][c] or
                (r, c) in path):
                return False
            
            path.add((r, c))
            res = (dfs(r + 1, c, i + 1) or
                   dfs(r - 1, c, i + 1) or
                   dfs(r, c + 1, i + 1) or
                   dfs(r, c - 1, i + 1))
            
            # initialize path for next process
            path.remove((r, c))
            return res
        
        for r in range(rows):
            for c in range(cols):
                # start process only if (value in cell) == (first char of word)
                if board[r][c] == word[0]:
                    if dfs(r, c, 0): return True
        return False

 

---

위와 유사한 문제가 백준 15705번 문제다.

백준 15705 문제 보기

 

문제 이해하기

위 문제와 거의 동일하나 탐색 규칙에 조금 차이가 있다.

본 문제의 경우, 상하좌우 및 대각선 탐색이 가능하며 중간에 탐색 방향이 바뀔 수 없다.

 

아이디어 구상

위 문제와 거의 동일한 흐름이다.

다만 여기서는 8방향 탐색 중간에 방향을 바꿀 수 없다.

때문에 dfs() 시, 각 탐색 case를 의미하는 status를 부여하고 이에 해당하는 방향으로만 탐색을 진행한다.

 

또한 print_result() 함수를 만들어, 단어 s를 grid에서 찾았다면 곧바로 1을 출력하고 프로그램을 종료하도록 구현했다.

 

풀이

전체 코드

s = input() # uppercase, len(s) <=100
n, m = map(int, input().split()) # 1 <= n: rows, m: columns <= 100
matrix = [list(input()) for _ in range(n)]

path = set() # to make sure not to revisit previous cell


def dfs(r, c, i, status): # (current r, current c, current character)
    # base case
    if i == len(s):
        return True
    if (r < 0 or c < 0 or r >= n or c >= m or
        matrix[r][c] != s[i] or
        (r, c) in path):
        return False

    path.add((r, c))
    if status == 0:
        res = dfs(r + 1, c, i + 1, 0)
    elif status == 1:
        res = dfs(r - 1, c, i + 1, 1)
    elif status == 2:
        res = dfs(r, c + 1, i + 1, 2)
    elif status == 3:
        res = dfs(r, c - 1, i + 1, 3)
    elif status == 4:
        res = dfs(r + 1, c - 1, i + 1, 4)
    elif status == 5:
        res = dfs(r - 1, c + 1, i + 1, 5)
    elif status == 6:
        res = dfs(r + 1, c + 1, i + 1, 6)
    elif status == 7:
        res = dfs(r - 1, c - 1, i + 1, 7)

    # initialize path for next process
    path.remove((r, c))
    return res


def print_result():
    for r in range(n):
        for c in range(m):
            # start process only if (value in cell) == (first char of s)
            if matrix[r][c] == s[0]:
                for status in range(8):
                    if dfs(r, c, 0, status):
                        print(1)
                        return
    print(0)
    return


print_result()

 

---

Leetcode 79. Word Search

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

 

백준 15705. 단어 찾기 (실버 2)

https://www.acmicpc.net/problem/15705​

 

 

 

 

-문제해결흐름을 간단히 정리한 주관적 포스팅-

 

-부족한 설명이 있다면 부디 조언 부탁드립니다-

 

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로,

이에 따른 일정액의 수수료를 제공받습니다