a-076-word-search2026-08-01mediumleetcode #79neetcode150

단어 검색

#array#string#backtracking#depth-first-search#matrix

문제

· problem

P.a-076-word-search

단어 검색

m×n 크기의 문자 그리드 board와 문자열 word가 주어질 때, word가 그리드에 존재하면 true를 반환하세요. 단어는 순차적으로 인접한 셀의 문자들로 구성될 수 있으며, 인접한 셀은 수평 또는 수직으로 이웃한 셀입니다. 같은 문자 셀은 한 번의 검색 경로 내에서 두 번 이상 사용될 수 없습니다.

제약

· 1 ≤ m, n ≤ 6
· 1 ≤ word.length ≤ 15
· board and word consist of only English letters

// 지문은 본인 언어 요약 — 원문은 위 링크에서

입출력 예시

example 1input → output

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCCED"

true

example 2input → output

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"SEE"

true

example 3input → output

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCB"

false

사전 사고

· pre-solve

● 1리스트 출력→● 2선택→● 3정답 공개

☐
같은 셀을 한 단어 검색 경로 내에서 여러 번 사용할 수 있나요?
☐
대각선 인접도 포함되나요?
☐
검색은 특정 셀에서 시작해야 하나요?
☐
시간 복잡도를 개선할 수 있는 방법이 있나요?
☐
방문한 셀을 추적하기 위해 2D 배열을 반드시 사용해야 하나요?
☐
각 재귀 단계에서 4개 방향을 모두 탐색해야 하나요?
☐
backtracking(방문 표시 제거)을 빠뜨리면 어떻게 되나요?

던질 질문에 체크하고 확인을 누르세요

// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)

논리 구조

· logic

● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개

// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.

step 1· 방문 추적 초기화

○

path = set()

○

path = []

○

visited = [[False] * len(board[0]) for _ in range(len(board))]

step 2· 기저 사례: 단어 완성│ 중첩

○

if i == len(word):

○

if i == len(word) - 1:

○

if i > len(word):

step 3· 위치와 문자 검증│ 중첩

○

if (

○

if r < 0 or c < 0 or r >= ROWS or c >= COLS:

○

if word[i] != board[r][c]:

step 4· 현재 셀 방문 표시│ 중첩

○

path.add((r, c))

○

path.add(r, c)

○

visited[r][c] = True

step 5· 4개 인접 셀 재귀 탐색│ 중첩

○

dfs(r + 1, c, i + 1)

○

dfs(r + 1, c, i + 1) only

○

dfs(r + 1, c, i) or dfs(r - 1, c, i) or dfs(r, c + 1, i) or dfs(r, c - 1, i)

step 6· Backtrack - 셀 방문 해제│ 중첩

○

path.remove((r, c))

○

path.discard((r, c))

○

# No backtracking

step 7· 최적화: 단어 역순 처리

○

count = sum(map(Counter, board), Counter())

○

if count[word[0]] < count[word[-1]]: word = word[::-1]

○

if len(word) > 5: word = word[::-1]

각 슬롯에 한 줄씩 골라보세요

// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.

문제풀이 · 트레이스

· solve

solution.py

class Solution:

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

        ROWS, COLS = len(board), len(board[0])

        path = set()

        def dfs(r, c, i):

            if i == len(word):

                return True

            if (

                min(r, 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

        # To prevent TLE,reverse the word if frequency of the first letter is more than the last letter's

        count = sum(map(Counter, board), Counter())

        if count[word[0]] > count[word[-1]]:

            word = word[::-1]

        for r in range(ROWS):

            for c in range(COLS):

                if dfs(r, c, 0):

                    return True

        return False

    # O(n * m * 4^n)

머릿속 dry-run 케이스

// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.

case 1

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCCED"

→

true

case 2

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"SEE"

→

true

case 3

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"ABCB"

→

false

// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.