LeetCode

LeetCode 79 Word Search 풀이: 방문 복원 백트래킹 DFS

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

  • 문제: 79. Word Search
  • 출처: LeetCode
  • 자체 판단 난이도: Level 3

격자의 모든 셀을 시작점으로 고려하고, 상하좌우로 이동하며 단어를 완성할 수 있는 모든 경로를 탐색해야 한다. 같은 셀을 한 경로에서 다시 사용할 수 없으므로 방문 상태를 관리하고 탐색 뒤 복원하는 백트래킹이 필요해 Level 3으로 판단했다.

1. 문제 요약

문자 격자 board와 문자열 word가 주어질 때, 격자에서 단어를 만들 수 있으면 True, 그렇지 않으면 False를 반환한다.

한 셀에서 다음 셀로 이동할 때는 상하좌우로 붙어 있는 셀만 사용할 수 있다. 대각선 이동은 허용되지 않으며, 하나의 셀은 같은 단어를 만드는 경로에서 한 번만 사용할 수 있다.

문제에서 중요한 조건은 다음과 같다.

  • 모든 셀을 단어의 시작점으로 사용할 수 있다.
  • 한 번의 이동은 상하좌우 중 하나다.
  • 현재 경로에서 같은 셀을 두 번 사용할 수 없다.
  • 단어의 모든 문자를 순서대로 맞춰야 한다.
  • 격자의 행과 열은 각각 최대 6, 단어 길이는 최대 15다.
  • 격자와 단어의 문자는 영문 대소문자로 이루어진다.

예를 들어 다음 격자에서는 A -> B -> C -> C -> B처럼 같은 셀을 다시 사용하는 경로는 허용되지 않는다. 문자가 같더라도 위치가 다른 셀인지, 현재 경로에서 이미 방문한 셀인지 구분해야 한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

후보 생성과 검증

DFS 상태를 (row, col, index)로 정의한다.

  • (row, col): 현재 단어 문자를 확인할 격자 위치
  • index: word[index]를 확인할 차례
  • 방문 표시: 현재 경로에서 이미 사용한 셀인지 나타내는 상태

모든 셀을 시작점으로 순회하며 다음 조건을 검사한다.

  1. index == len(word)이면 단어의 모든 문자를 찾았으므로 True를 반환한다.
  2. 격자 밖이거나 현재 셀의 문자가 word[index]와 다르면 해당 경로를 종료한다.
  3. 현재 셀이 이미 방문 중이면 같은 셀을 재사용할 수 없으므로 종료한다.
  4. 현재 셀을 방문 처리한 뒤 네 방향으로 다음 문자를 탐색한다.
  5. 네 방향 탐색이 끝나면 방문 표시를 해제하고 이전 상태로 돌아간다.

현재 셀을 방문 처리한 뒤 네 방향을 모두 확인하고 표시를 해제해야 다른 시작점이나 다른 경로가 같은 셀을 다시 사용할 수 있다. 이 과정을 백트래킹이라고 한다.

방문 표시는 현재 경로에서만 유지해야 하는 이유

방문 상태는 전체 탐색에서 영구적으로 유지되는 방문 기록이 아니다. 한 경로 안에서는 같은 셀을 막아야 하지만, 그 경로가 실패하고 되돌아오면 해당 셀은 다른 경로에서 사용할 수 있어야 한다.

따라서 전역 visited를 계속 유지하면 이미 실패한 경로가 다른 시작점의 탐색까지 막게 된다. 현재 재귀 호출의 범위에서만 셀을 표시하고, 재귀가 끝나는 즉시 원래 상태로 복원해야 한다.

방문 상태를 격자에 직접 표시하기

별도의 visited 집합을 만들 수도 있지만, 이 풀이에서는 현재 셀의 문자를 임시 기호 #로 바꾸어 방문 여부를 표시한다. 문제의 격자에는 영문자만 들어오므로 #는 원래 값과 충돌하지 않는다. 탐색 전 원래 문자를 저장해 두었다가 재귀가 끝난 뒤 복원하면 추가 방문 집합 없이 같은 효과를 얻을 수 있다.

시간·공간 복잡도

격자의 모든 셀에서 시작할 수 있으므로 시작점은 R * C개다. 각 단계에서 최대 네 방향을 확인하고 단어 길이를 L이라고 하면 시간 복잡도는 최악의 경우 O(R * C * 4^L)로 표현할 수 있다. 한 번 방문한 셀로 즉시 돌아가는 선택까지 제외하면 실제 분기 수는 더 작지만, 이 상한으로 충분히 설명할 수 있다.

격자를 직접 방문 표시하므로 별도의 방문 배열은 만들지 않는다. 재귀 깊이가 단어 길이 만큼 증가하므로 추가 공간 복잡도는 호출 스택 기준 O(L)다.

3. 문제 해결 코드 (Python)

class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows = len(board)
        cols = len(board[0])

        def dfs(row: int, col: int, index: int) -> bool:
            if index == len(word):
                return True

            if (
                row < 0
                or row >= rows
                or col < 0
                or col >= cols
                or board[row][col] != word[index]
            ):
                return False

            original = board[row][col]
            board[row][col] = "#"

            found = (
                dfs(row + 1, col, index + 1)
                or dfs(row - 1, col, index + 1)
                or dfs(row, col + 1, index + 1)
                or dfs(row, col - 1, index + 1)
            )

            board[row][col] = original
            return found

        for row in range(rows):
            for col in range(cols):
                if dfs(row, col, 0):
                    return True

        return False

#로 표시된 셀은 현재 경로에서 다시 검사해도 word[index]와 일치하지 않으므로 자연스럽게 재사용이 차단된다. found가 True인 경우에도 현재 셀을 원래 문자로 복원한 뒤 반환하므로 함수 호출 후 입력 격자가 변경된 상태로 남지 않는다.

4. 오답 접근과 반례

방문 표시를 복원하지 않는 경우

방문한 셀을 계속 #로 두면 한 경로에서 실패한 뒤 다른 경로가 해당 셀을 사용할 수 없다. 다음 입력에서는 첫 번째 A에서 시작한 일부 경로가 실패하더라도 다른 방향으로 돌아가 B를 찾아야 한다.

board = [["A", "B"], ["C", "D"]]
word = "ACDB"
정답 = True

경로는 A -> C -> D -> B다. 이전 탐색에서 C나 D를 영구적으로 방문 처리하면 이 유효한 경로를 놓칠 수 있으므로 반드시 재귀가 끝날 때 복원해야 한다.

대각선으로 이동하기

문자 위치가 가까워 보여도 대각선 이동은 허용되지 않는다. 예를 들어 다음 입력에서 A와 C는 대각선으로만 이어져 있으므로 "AC"를 만들 수 없다.

board = [["A", "B"], ["C", "D"]]
word = "AC"
정답 = False

상하좌우 네 방향만 재귀 호출에 포함해야 한다.

셀의 문자가 같다는 이유로 위치를 구분하지 않는 경우

같은 문자가 여러 셀에 있어도 각각은 서로 다른 위치다. 단순히 사용한 문자 종류를 집합에 넣으면 A라는 문자를 여러 위치에서 사용하는 상황을 잘못 막거나 허용할 수 있다. 방문 상태는 문자 값이 아니라 (row, col) 위치별로 관리해야 한다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 탐색 성공, 실패, 셀 재사용 금지 조건을 확인할 수 있다.

solver = Solution()
assert solver.exist([list("ABCE"), list("SFCS"), list("ADEE")], "ABCCED") is True
assert solver.exist([list("ABCE"), list("SFCS"), list("ADEE")], "ABCB") is False
assert solver.exist([["A", "B"], ["C", "D"]], "ABA") is False

5. 공식 예제와 추가 검증

작성한 exist 함수를 Python으로 실행해 공식 예제와 경계 사례를 확인했다. 각 테스트는 입력 격자를 복사해 전달했으며, 탐색 후 격자가 원래 상태로 복원되는지도 함께 확인했다.

공식 예제

입력 기대 출력 확인 결과
board=[[A,B,C,E],[S,F,C,S],[A,D,E,E]], word="ABCCED" True 통과
board=[[A,B,C,E],[S,F,C,S],[A,D,E,E]], word="SEE" True 통과
board=[[A,B,C,E],[S,F,C,S],[A,D,E,E]], word="ABCB" False 통과

추가 검증 1: 한 칸 격자

입력: board = [["A"]], word = "A"
기대 출력: True
확인 결과: 통과
검증 목적: 최소 격자와 길이 1인 단어 처리 확인

추가 검증 2: 같은 셀 재사용 금지

입력: board = [["A", "B"], ["C", "D"]], word = "ABA"
기대 출력: False
확인 결과: 통과
검증 목적: A 셀 하나를 두 번 사용하는 경로를 허용하지 않는지 확인

추가 검증 3: 백트래킹으로 다른 경로 탐색

입력: board = [["A", "B"], ["C", "D"]], word = "ACDB"
기대 출력: True
확인 결과: 통과
검증 목적: 실패한 경로의 방문 상태를 복원하고 다른 경로를 시도하는지 확인

6. 다른 풀이 방식 검색 및 비교

  • Word Search 공식 문제는 상하좌우 인접 셀을 사용하고 같은 셀을 한 번만 사용하는 단어 탐색 조건을 정의한다.
  • NeetCode의 Word Search 설명은 시작점별 DFS, 방문 집합, 방문 배열과 격자 직접 표시 방식을 비교한다.

별도의 visited 집합이나 2차원 방문 배열을 사용해도 같은 백트래킹 구조로 해결할 수 있다. 그 방식은 입력 격자를 직접 바꾸지 않는다는 장점이 있지만, 방문 상태를 별도로 저장하는 O(L) 또는 O(R * C) 공간이 필요하다. 이 글에서는 문자를 임시로 바꾸고 반드시 복원해 추가 방문 자료구조를 사용하지 않는 방식을 선택했다.

마무리

Word Search는 모든 시작점에서 단어를 한 글자씩 따라가되, 현재 경로에서 이미 사용한 셀을 재사용하지 않는 문제다. 셀을 방문 표시한 뒤 네 방향을 탐색하고 원래 문자로 복원하는 백트래킹을 사용하면 경로별 방문 제약과 다른 경로로의 재탐색을 동시에 처리할 수 있다.

#백트래킹#LeetCode#난이도 3