파이썬으로 2D 보드에서 단어 검색 구현하기 — 백트래킹 알고리즘 완벽 가이드

2차원(2D) 보드와 하나의 단어가 주어졌을 때, 해당 단어가 그리드 안에 존재하는지 판별하는 문제를 파이썬으로 해결해 보겠습니다.

문제 정의

단어는 순차적으로 인접한 셀들의 문자를 연결하여 만들 수 있습니다. 여기서 '인접(adjacent)' 셀이란 가로 또는 세로 방향으로 이웃한 셀을 의미합니다. 중요한 제약 조건은 같은 셀의 문자를 두 번 이상 사용할 수 없다는 점입니다.

예를 들어 다음과 같은 보드가 있다고 가정해 봅시다.

A	B	C	E
S	F	C	S
A	D	E	F

단어 "ABCCED" → true (경로가 존재)
단어 "SEE" → true (경로가 존재)
단어 "ABCB" → false (B를 재사용해야 하므로 불가능)

풀이 전략: 재귀 + 백트래킹

이 문제는 재귀적 탐색과 백트래킹(backtracking)을 활용하여 해결할 수 있습니다. 핵심 아이디어는 각 셀에서 출발해 상하좌우 네 방향으로 단어의 다음 문자를 찾아 나가되, 이미 방문한 셀은 임시로 막아두는 것입니다.

알고리즘 단계

재귀 함수 find()는 매개변수로 행렬 mat, 단어 word, 행 row, 열 col, 그리고 현재 인덱스 i(초기값 0)를 받습니다.
i가 단어의 길이와 같으면 모든 문자를 찾은 것이므로 True를 반환합니다.
행이나 열이 보드 범위를 벗어나거나, word[i]가 mat[row][col]과 일치하지 않으면 False를 반환합니다.
현재 셀을 '*'로 변경하여 방문 처리를 합니다. (재방문 방지)
상·하·좌·우 네 방향에 대해 재귀적으로 find()를 호출하고, 하나라도 성공하면 결과를 저장합니다.
탐색이 끝나면 현재 셀을 원래 문자 word[i]로 복원합니다. 이것이 바로 백트래킹의 핵심입니다.
결과 res를 반환합니다.

메인 로직

행 개수 n과 열 개수 m을 구합니다.
모든 셀을 순회하면서 word[0]과 일치하는 셀을 찾습니다.
일치하는 셀에서 find()를 호출하고, False가 아니면 True를 즉시 반환합니다.
끝까지 성공하지 못하면 False를 반환합니다.

파이썬 구현 코드

class Solution(object):
    def exist(self, board, word):
        n = len(board)
        m = len(board[0])
        for i in range(n):
            for j in range(m):
                if word[0] == board[i][j]:
                    if self.find(board, word, i, j):
                        return True
        return False

    def find(self, board, word, row, col, i=0):
        # 모든 문자를 찾았으면 성공
        if i == len(word):
            return True
        # 범위 초과 또는 문자 불일치 시 실패
        if row >= len(board) or row < 0 or col >= len(board[0]) or col < 0 or word[i] != board[row][col]:
            return False
        # 방문 처리
        board[row][col] = '*'
        # 네 방향 재귀 탐색
        res = self.find(board, word, row+1, col, i+1) or \
              self.find(board, word, row-1, col, i+1) or \
              self.find(board, word, row, col+1, i+1) or \
              self.find(board, word, row, col-1, i+1)
        # 백트래킹: 원래 문자 복원
        board[row][col] = word[i]
        return res

ob1 = Solution()
print(ob1.exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE"))

실행 결과

입력

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

출력

True

복잡도 분석

시간 복잡도: O(N × M × 4^L) — N×M 크기의 보드의 각 셀에서 시작할 수 있으며, 각 탐색마다 최대 4방향으로 단어 길이 L만큼 깊이 진행합니다.
공간 복잡도: O(L) — 재귀 호출 스택의 최대 깊이는 단어의 길이에 비례합니다.

마무리

이 문제의 핵심은 방문 처리 후 반드시 복원하는 백트래킹입니다. 복원 과정이 없으면 한 번의 탐색에서 사용된 셀이 다른 시작점의 탐색에 영향을 주어 잘못된 결과를 얻게 됩니다. 이 패턴은 미로 찾기, 스도쿠, N-Queen 등 다양한 그리드 탐색 문제에 응용될 수 있으니 꼭 익혀두시기 바랍니다.