Word Search

Q: Word Search의 시간 복잡도는 얼마인가요?

m × n 보드와 길이가 L 인 단어의 경우 O(m·n·3^L) 입니다. 모든 셀에서 경로를 시작할 수 있고, 첫 번째 단계 이후 각 셀에는 방문하지 않은 이웃이 최대 3개 있습니다. 추가 공간은 재귀를 위한 O(L) 에 보드 복사본을 위한 O(m·n) 을 더한 것입니다.

보통백트래킹 그래프

+10

문자 격자 board와 문자열 목록이 주어집니다. 여기서 board[r][c]는 행 r, 열 c에 있는 문자이며, 문자열 word도 주어집니다.

word를 추적할 수 있으면 true를 반환하세요. 임의의 셀에서 시작해 매번 위, 아래, 왼쪽 또는 오른쪽 셀로 이동하여 방문한 셀의 문자를 순서대로 이어 붙였을 때 word가 되어야 하며, 같은 셀을 두 번 사용해서는 안 됩니다. 그렇지 않으면 false를 반환하세요. 문자는 대소문자를 구분합니다.

함수

exist(board: string-array, word: string) → boolean

boardstring-array: 격자, 행마다 하나의 문자 문자열
wordstring: 추적할 단어
반환값boolean: 단어를 인접한 셀을 따라 추적할 수 있는지 여부(각 셀은 최대 한 번만 사용)

제약 조건

1 ≤ board.length ≤ 6
1 ≤ board[i].length ≤ 6이고 모든 행의 길이는 같습니다.
1 ≤ word.length ≤ 20
board와 word에는 대문자와 소문자의 영어 알파벳 문자만 포함되어 있습니다.

예제

입력: board = ["STAR", "POOL", "ENDS"]word = "STOOLS"
출력: true
설명: 왼쪽 위의 S에서 시작해 T까지 오른쪽으로 이동하고, O까지 아래로 이동한 다음, O와 L까지 오른쪽으로 이동하고, L 아래의 S까지 아래로 이동하세요. 반복되는 셀은 없습니다.

입력: board = ["STAR", "POOL", "ENDS"]word = "POP"
출력: false
설명: 보드에는 P가 하나 있습니다. P와 O 다음에는 또 다른 P가 필요하지만, 유일한 P는 시작 칸에 있으며 두 번 사용할 수 없습니다.

입력: board = ["STAR", "POOL", "ENDS"]word = "SAND"
출력: false
설명: SAND의 모든 글자가 보드에 있지만, 0행 2열에 있는 유일한 A는 어느 S와도 인접하지 않습니다.

후속 질문

word의 서로 다른 추적 경로가 보드에 몇 개 있는지 세어 볼 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

격자를 통과하는 경로를 찾아야 합니다. 백트래킹은 한 번에 한 글자씩 경로를 확장하며, 경로가 셀을 사용하는 동안 각 셀을 표시하고 되돌아오면서 표시를 해제하므로 어떤 경로도 셀을 재사용하지 않습니다. 이 탐색의 시간 복잡도는 단어 길이에 대해 지수적이며, 6 × 6 보드에서는 가능합니다.

방문한 칸을 기록하는 그리드로 백트래킹하기

핵심 아이디어

처음 i개의 글자를 나타내는 경로는 word[i]가 있고 경로에 포함되지 않은 이웃 칸으로 이어집니다. 그런 이웃 칸이 없으면 막다른 길이므로 되돌아갑니다.

표시를 해제하는 것이 이 방법을 올바르게 만듭니다. 막다른 길에서 지나간 칸은 다음 시도에서 다시 사용할 수 있어야 합니다. AA / AB 보드에서 AAA를 찾을 때 왼쪽 위에서 시작하는 두 시도는 모두 막힙니다. 해당 칸의 표시가 그대로 남아 있다면 왼쪽 아래, 왼쪽 위, 오른쪽 위 순서의 답을 찾지 못하게 됩니다.

첫 번째 이동 후에는 각 단계에서 새로 탐색할 수 있는 방향이 최대 세 개이므로, 최대 m·n·3^L개의 경로를 탐색할 수 있습니다. A로 된 5 × 5 보드에서 A 8개 뒤에 B가 오는 경우, false라고 답하기 전에 약 53,000개의 칸을 확인합니다.

알고리즘

visited 그리드를 만들고, 모든 값을 false로 설정합니다.
dfs(r, c, i): (r, c)가 그리드 범위 밖에 있거나, 방문한 상태이거나, word[i]가 아니면 false를 반환합니다. i가 마지막 인덱스이면 true를 반환합니다.
그렇지 않으면 (r, c)를 표시하고, i+1을 사용해 네 이웃을 확인한 다음 표시를 해제하고, 하나라도 성공했는지 반환합니다.
어떤 셀에서든 dfs(r, c, 0)이 성공하면 true를 반환합니다.

def exist(board, word):
    rows, cols = len(board), len(board[0])
    visited = [[False] * cols for _ in range(rows)]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if visited[r][c] or board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        visited[r][c] = True   # mark: the current path owns this cell
        found = (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))
        visited[r][c] = False  # restore: other paths may use it
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

제자리 표시와 가지치기를 이용한 백트래킹

핵심 아이디어

검색은 유지하되 두 가지를 바꿉니다. 보드의 복사본에서 칸에 #를 써서 표시하고, 돌아올 때 원래 문자를 복원합니다. #는 단어의 어떤 문자와도 일치하지 않으므로, 문자 검사에서 경로상의 칸도 제외됩니다.

그다음 가지치기를 합니다. 단어에 보드에 있는 것보다 특정 문자가 더 많이 필요하면 false를 반환합니다. 이렇게 하면 검색 없이 모든 칸이 A인 보드에 답할 수 있습니다. 경로를 거꾸로 읽으면 같은 칸에서 뒤집은 단어가 만들어지므로, 뒤집은 단어를 검색해도 답은 같습니다. 보드에서 더 드문 문자가 있는 쪽 끝에서 시작합니다. 시작할 수 있는 칸이 더 적고, 잘못된 시작은 즉시 실패합니다.

두 개의 C 사이 모서리에 유일한 B가 있는 경우, 정방향 검색은 약 35,000번의 칸 검사를 수행하지만, 역방향 검색은 27번 수행합니다. 최악의 경우에도 O(m·n·3^L)입니다.

알고리즘

단어에 필요한 특정 문자가 보드에 있는 것보다 더 많으면 false를 반환합니다.
보드에 마지막 문자보다 word[0]이 더 많이 있으면 word를 뒤집습니다.
보드를 변경할 수 있는 격자에 복사합니다.
dfs(r, c, i): 셀이 word[i]가 아니면 실패합니다. 마지막 인덱스라면 성공합니다. 그렇지 않으면 해당 셀을 #으로 설정하고, 범위 안에 있는 각 이웃 셀에 i+1을 사용해 시도한 다음, 셀을 복원하고 하나라도 성공했는지 반환합니다.
어떤 셀에서든 dfs가 성공하면 true를 반환합니다.

from collections import Counter


def exist(board, word):
    rows, cols = len(board), len(board[0])

    # Pruning 1: the board must hold every letter as many times as the word uses it.
    have = Counter("".join(board))
    for letter, need in Counter(word).items():
        if have[letter] < need:
            return False

    # Pruning 2: a path read backwards is the same path, so start from the
    # end whose letter is rarer on the board: fewer cells begin a search.
    if have[word[0]] > have[word[-1]]:
        word = word[::-1]

    grid = [list(row) for row in board]

    def dfs(r, c, i):
        # Can word[i:] be traced starting at cell (r, c)?
        if grid[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        grid[r][c] = "#"  # mark: "#" matches no letter, so this path cannot reuse the cell
        found = False
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < rows and 0 <= nc < cols and dfs(nr, nc, i + 1):
                found = True
                break
        grid[r][c] = word[i]  # restore the letter for other paths
        return found

    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

함정과 경계 사례

실패한 분기 이후 셀의 표시를 해제하지 않음: AA에서 AA / AB를 찾으면 false가 반환됩니다.
표시를 전혀 하지 않음: 경로가 마지막 셀로 되돌아오며, 예시 보드에서 POP을 찾으면 true가 반환됩니다.
경계를 확인하기 전에 셀을 읽음: Python에서는 board[-1]이 마지막 행이므로 경로가 격자를 돌아서 이어집니다.
이동한 뒤에만 성공 여부를 확인함: ["A"]에서 A를 찾으면 true가 반환되어야 합니다.
셀의 대소문자를 바꿔 표시함: ["aA"]에서 표시된 a는 두 번째 A로 읽히므로 aAA를 찾으면 true가 반환됩니다.

자주 묻는 질문3

Word Search의 시간 복잡도는 얼마인가요?

m × n 보드와 길이가 L인 단어의 경우 O(m·n·3^L)입니다. 모든 셀에서 경로를 시작할 수 있고, 첫 번째 단계 이후 각 셀에는 방문하지 않은 이웃이 최대 3개 있습니다. 추가 공간은 재귀를 위한 O(L)에 보드 복사본을 위한 O(m·n)을 더한 것입니다.

가지치기는 Word Search를 어떻게 더 빠르게 만들까요?

먼저 문자의 수를 세고, 보드에 한쪽 문자가 너무 적으면 false를 반환하세요. 그런 다음 더 드문 문자를 사용해 끝에서부터 검색하세요. 더 적은 수의 칸에서 시작할 수 있기 때문입니다. 두 검사 모두 최악의 경우를 바꾸지는 않습니다.

Word Search와 Word Search II의 차이점은 무엇인가요?

Word Search II는 목록의 단어 중 어떤 단어가 보드에 있는지 묻습니다. 단어마다 한 번씩 검색하면 작업이 반복되므로, 일반적인 해결 방법은 단어를 트라이에 넣고 보드를 한 번 탐색하면서 현재 문자들로 시작하는 단어가 없으면 경로를 중단하는 것입니다.

def exist(board, word):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

board = ["STAR", "POOL", "ENDS"]
word = "STOOLS"

예상 출력

true