Word Search

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

최악의 경우는 m × n 보드와 길이가 L 인 단어에 대해 O(m·n·3^L) 입니다. m·n 개의 각 셀에서 경로를 시작할 수 있으며, 첫 번째 단계 이후 각 셀에는 시도할 수 있는 방문하지 않은 이웃이 최대 세 개 있습니다. 추가 공간은 재귀 호출에 O(L) 이며, 표시를 위해 보드를 복사하는 경우 O(m·n) 이 더 필요합니다.

보통백트래킹 그래프

+10

문자 격자 board가 주어집니다. 이 격자는 문자열 목록으로 주어지며, board[r][c]는 r행 c열의 문자입니다. 문자열 word도 주어집니다.

격자에서 word를 추적할 수 있으면 true를 반환하세요. 임의의 셀에서 시작해 매번 현재 셀의 바로 위, 아래, 왼쪽 또는 오른쪽 셀로 이동하여, 방문한 셀의 문자들이 순서대로 word를 이루면 됩니다. 추적 중 같은 셀을 두 번 사용할 수 없습니다. 그렇지 않으면 false를 반환하세요. 문자는 대소문자를 구분하므로 a와 A는 서로 다릅니다.

함수

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
설명: 0행 0열의 S에서 시작한 다음 오른쪽으로 가서 T에 도달하고, 아래로 가서 O에 도달한 뒤, 오른쪽으로 가서 두 번째 O에 도달하고, 오른쪽으로 가서 L에 도달한 다음, 아래로 가서 2행 3열의 S에 도달하세요. 이렇게 하면 서로 다른 셀 여섯 개를 지나며, 각 셀은 바로 앞의 셀과 인접해 있습니다.

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

입력: board = ["STAR", "POOL", "ENDS"]word = "SAND"
출력: false
설명: SAND의 모든 글자가 보드에 있지만, 첫 번째 단계에서 경로가 끊깁니다. 유일한 A는 0행 2열에 있고, 어느 S도 그 글자에 닿아 있지 않습니다.

제출 시 숨은 테스트 +23개

후속 질문

예 또는 아니요 대신, 보드에 word의 서로 다른 경로가 몇 개 있는지 세어 볼 수 있나요?

힌트

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

3개 중 0개 열림

풀이

이 문제에는 공식을 적용해 답을 구할 수 없습니다. 격자를 통과하는 경로를 탐색해야 합니다. 백트래킹은 한 번에 하나의 경로를 탐색합니다. 경로에 글자를 하나씩 추가하고, 경로가 각 칸을 사용하는 동안 표시해 두었다가 되돌아갈 때 표시를 해제합니다. 따라서 한 경로 안에서는 같은 칸을 다시 사용할 수 없지만, 다른 모든 경로에서는 해당 칸을 자유롭게 사용할 수 있습니다. 최악의 경우 이 탐색은 단어 길이에 대해 지수적으로 증가하지만, 최대 6 × 6 크기의 보드에서는 괜찮습니다. 그 전에 간단한 검사 두 가지를 수행하면 작업량을 수만 단계에서 수십 단계로 줄이는 경우가 많습니다. 하나는 글자 수를 세는 것이고, 다른 하나는 단어에서 더 드문 글자가 있는 쪽 끝부터 탐색을 시작하는 것입니다.

방문한 칸을 기록하는 격자를 사용한 백트래킹

핵심 아이디어

의사 결정 트리를 떠올려 보세요. 첫 번째 선택은 시작 셀이며, 그 셀에는 word[0]이 있어야 합니다. 그다음부터 각 노드는 처음 i개의 문자를 나타내는 경로이고, 자식 노드는 word[i]를 포함하며 아직 경로에 포함되지 않은 이웃 셀입니다. 단어 전체를 나타내는 경로는 성공입니다. 그런 이웃이 없는 경로는 막다른 길이므로, 한 단계 되돌아가 다음 선택을 시도합니다.

visited 그리드는 각 셀을 한 번만 사용할 수 있다는 규칙을 적용합니다. 경로가 셀에 들어갈 때 표시하고, 경로가 셀에서 나올 때 표시를 해제합니다. 이 표시 해제가 백트래킹의 핵심입니다. 막다른 길에서 지나간 셀을 다음 시도에서는 다시 사용할 수 있어야 합니다. AA / AB 보드에서 단어가 AAA일 때 왼쪽 위 셀에서 시작한다고 해 봅시다. 아래로 가면 왼쪽 아래에서 막힙니다(다른 이웃은 B입니다). 오른쪽으로 가도 오른쪽 위에서 막힙니다. 이 셀들의 표시가 그대로 남아 있다면 왼쪽 아래, 왼쪽 위, 오른쪽 위 순서로 이어지는 답은 절대 찾을 수 없습니다.

이 방법은 표준적인 풀이이며, 여기서는 정확하고 충분히 빠릅니다. 비용은 탐색하는 경로의 수입니다. 첫 번째 이동 이후에는 각 단계에서 새 방향이 최대 세 개이므로, 길이가 L인 단어는 대략 m·n·3^L개의 경로를 의미할 수 있습니다. 모든 칸이 A인 5 × 5 보드와, A 8개 뒤에 B가 오는 단어를 생각해 보세요. A로 이루어진 모든 경로는 유효한 접두사이므로, 탐색은 B가 없다는 것을 알아내기 전에 모든 경로를 살펴봅니다. false라고 답하기 위해 약 65,000번의 셀 확인이 필요합니다. 문자가 하나 추가될 때마다 그 횟수는 대략 두 배가 됩니다. 그래서 다음 방법에서는 탐색하기 전에 몇 가지를 확인합니다.

알고리즘

보드 크기의 visited 그리드를 만들고, 모든 값을 false로 설정합니다.
dfs(r, c, i)를 정의합니다. (r, c)가 그리드 밖에 있거나, 방문한 위치이거나, 해당 위치의 문자가 word[i]가 아니면 false를 반환합니다.
i가 word의 마지막 인덱스이면 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가 8개이고 B는 없는 보드의 경우, 약 65,000번 확인하는 대신 탐색을 전혀 하지 않고 답을 구할 수 있습니다. 더 드문 문자 쪽에서 시작하세요. 경로를 거꾸로 읽어도 같은 셀들에서 뒤집힌 단어가 만들어지므로, 대신 뒤집힌 단어를 탐색해도 됩니다. 보드에서 마지막 문자가 첫 문자보다 더 드물다면 단어를 뒤집으세요. 탐색을 시작할 수 있는 셀이 줄어들고, 드문 문자가 마지막 단계가 아니라 첫 단계에서 잘못된 시작점을 걸러냅니다.

드문 문자가 존재하지만 도달할 수 없을 때 두 번째 규칙이 중요합니다. 유일한 B를 두 이웃 셀이 C인 모서리에 두고, 8개의 A 다음에 B가 오는 단어를 탐색해 보세요. 문자 개수 검사는 통과합니다. 정방향으로는 탐색이 여전히 모든 A 경로를 따라가며, 셀을 약 35,000번 확인합니다. 반대로 뒤집으면 단어가 B로 시작하고, 시작할 수 있는 셀은 하나뿐이며, 그 이웃들은 A가 아니므로 탐색은 약 30번 확인한 뒤 끝납니다.

최악의 경우는 여전히 O(m·n·3^L)입니다. 문자가 균형을 이루고 막다른 경로가 늦게 나타나는 보드와 단어를 만들 수 있습니다. 가지치기는 답이나 복잡도 상한을 바꾸지 않습니다. 문자를 세기 위한 한 번의 순회만 추가하는 대신, 일반적인 탐색이 시간을 낭비하는 흔한 경우들을 제거하며, 단어의 길이가 길어질수록 그 차이는 빠르게 커집니다.

알고리즘

보드와 단어에서 각 문자의 개수를 센다. 단어에 필요한 문자 수가 보드에 있는 문자 수보다 많으면 false를 반환한다.
보드에 있는 word[0]의 개수가 마지막 문자의 개수보다 많으면 word를 뒤집는다.
변경할 수 있는 문자 그리드에 보드를 복사한다.
dfs(r, c, i)를 정의한다. 셀이 word[i]가 아니면 실패를 반환하고, i가 마지막 인덱스이면 성공을 반환한다. 그렇지 않으면 셀을 #으로 설정하고, 범위 안에 있는 각 이웃 셀에 대해 i+1로 시도한 다음 문자를 원래대로 돌려놓고, 성공한 시도가 하나라도 있는지 반환한다.
모든 셀에서 dfs(r, c, 0)을 실행하고, 하나라도 성공하면 즉시 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 / AB에서는 단어 AAA가 false로 나옵니다.
방문 표시를 전혀 하지 않는 경우. 방문 표시가 없으면 경로가 이전에 지나온 셀로 다시 이동할 수 있고, 예시 보드에서 POP은 true를 반환합니다.
경계를 확인하기 전에 셀을 읽는 경우. Python에서 board[-1]은 오류가 아니라 마지막 행이므로, 경계 검사를 빠뜨리면 그리드가 조용히 순환됩니다.
이동한 뒤에만 성공 여부를 확인하는 경우. 한 셀짜리 보드 ["A"]에서 한 글자 단어 A를 찾으면, 셀에 이웃이 없어도 true를 반환해야 합니다.
실제 글자로 사용될 수 있는 문자로 방문 표시를 하는 경우. 예를 들어 셀의 대소문자를 바꾸면 a와 A를 모두 사용하는 보드에서 문제가 생깁니다.
대각선으로 이동하는 경우. 변을 공유하는 네 개의 셀만 이웃으로 간주합니다.

자주 묻는 질문4

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

최악의 경우는 m × n 보드와 길이가 L인 단어에 대해 O(m·n·3^L)입니다. m·n개의 각 셀에서 경로를 시작할 수 있으며, 첫 번째 단계 이후 각 셀에는 시도할 수 있는 방문하지 않은 이웃이 최대 세 개 있습니다. 추가 공간은 재귀 호출에 O(L)이며, 표시를 위해 보드를 복사하는 경우 O(m·n)이 더 필요합니다.

단어 찾기에서 셀의 표시를 왜 해제하나요?

표시는 해당 셀이 현재 경로에 있음을 의미합니다. 분기가 실패하면 셀은 경로에서 벗어나며, 다른 경로에서 그 셀이 필요할 수 있습니다. 표시를 유지하면 이후 탐색에서 해당 셀을 사용된 것으로 간주하여 유효한 경로 찾기를 놓칠 수 있습니다. 들어갈 때 표시하고, 나올 때 표시를 해제하세요.

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

검색 전에 두 가지 검사를 수행합니다. 단어에 필요한 특정 문자의 개수가 보드에 있는 개수보다 많으면 검색하지 않고도 false를 반환할 수 있습니다. 또한 경로를 거꾸로 읽어도 뒤집힌 단어가 되므로, 더 드문 문자가 있는 쪽 끝에서 시작하면 시작 셀의 수를 줄이고 잘못된 경로를 더 빨리 중단할 수 있습니다. 어느 쪽도 최악의 경우를 바꾸지는 않으며, 기본 검색만으로도 완전한 답을 얻을 수 있습니다. A로 채워진 5 × 5 보드에서 없는 B가 필요한 단어를 찾을 때, 이 검사들은 약 65,000회의 셀 확인을 0회로 줄여 줍니다.

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

Word Search는 단어 하나에 대해 묻습니다. Word Search II는 단어 목록을 주고 그중 어떤 단어가 보드에 나타나는지 묻습니다. 단어마다 이 검색을 한 번씩 실행하면 많은 작업이 반복되므로, 일반적인 해결 방법은 모든 단어를 트라이에 넣고 보드를 한 번 탐색하면서, 현재까지의 문자로 시작하는 단어가 더 이상 없으면 즉시 해당 경로를 중단하는 것입니다.

Python

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

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

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

기대값

true