Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 그리드에서 단어 찾기: DFS·백트래킹 상하좌우 탐색 구현

문제 소개

그리드(격자) 또는 2차원 행렬 형태로 배치된 문자들이 주어졌을 때, 특정 단어가 이 그리드 안에 존재하는지 확인하는 문제를 생각해 보겠습니다. 단어는 네 가지 방향, 즉 좌우 수평 방향과 상하 수직 방향으로만 읽을 수 있으며 대각선 이동은 허용되지 않습니다. 단어를 찾으면 True, 찾지 못하면 False를 반환하면 됩니다.

예를 들어 입력이 다음과 같다고 가정해 봅시다.

pghsf
ykdgh
tkghi
hnsjs
ojfgh
nrtyu

이때 찾을 단어가 'python'이라면 결과는 True입니다. 왼쪽 위 칸의 'p'에서 시작해 한 칸씩 아래로 내려가면 첫 번째 열을 따라 p → y → t → h → o → n 순서로 단어가 완성되기 때문입니다.

접근 방법: 깊이 우선 탐색(DFS)과 백트래킹

이 문제는 DFS(깊이 우선 탐색)와 백트래킹을 조합하면 자연스럽게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 그리드의 모든 칸을 잠재적인 시작점으로 삼습니다.
  • 현재 칸의 문자가 찾고자 하는 단어의 해당 위치 문자와 일치하면, 상하좌우 네 방향으로 재귀적으로 탐색을 이어갑니다.
  • 이미 방문한 칸을 '#' 같은 임시 문자로 덮어 써 같은 칸을 두 번 사용하지 않도록 하고, 탐색이 끝나면 원래 문자로 되돌립니다(백트래킹).
  • 단어의 모든 문자를 매칭하면 True를 반환하고, 어떤 경로로도 완성하지 못하면 False를 반환합니다.

find_grid() 함수의 동작 단계

  1. 종료 조건: degree(현재까지 매칭한 문자 수)가 단어 길이와 같으면 True를 반환합니다.
  2. 범위 검사: 현재 위치가 그리드를 벗어나면(음수 좌표 또는 행·열 개수 초과) False를 반환합니다.
  3. 문자 일치 검사: matrix[row_pos][col_pos]가 input_str[degree]와 같다면,
    • 현재 값을 temp에 저장하고 해당 칸을 '#'로 바꿔 방문 표시를 합니다.
    • 상·하·좌·우 네 방향으로 degree + 1을 넘겨 재귀 호출한 결과를 OR로 결합합니다.
    • 탐색이 끝나면 칸을 temp로 복원하고 result를 반환합니다.
  4. 일치하지 않으면 False를 반환합니다.

메인 함수(solve)의 동작 단계

  1. 단어 길이가 행 개수 × 열 개수보다 크면 그리드에 존재할 수 없으므로 False를 반환합니다.
  2. 모든 행과 열을 순회하면서 matrix[row][col]이 단어의 첫 글자와 일치하는 칸을 찾습니다.
  3. 일치하는 칸마다 find_grid()를 호출해 True가 나오면 즉시 True를 반환합니다.
  4. 모든 시작점을 시도해도 실패하면 False를 반환합니다.

구현 예제

다음은 위 알고리즘을 파이썬으로 구현한 코드입니다.

def find_grid(matrix, input_str, row_pos, col_pos, row_count, col_count, degree):
    if degree == len(input_str):
        return True
    if row_pos < 0 or col_pos < 0 or row_pos >= row_count or col_pos >= col_count:
        return False
    if matrix[row_pos][col_pos] == input_str[degree]:
        temp = matrix[row_pos][col_pos]
        matrix[row_pos][col_pos] = '#'
        result = (find_grid(matrix, input_str, row_pos - 1, col_pos, row_count, col_count, degree + 1)
              or find_grid(matrix, input_str, row_pos + 1, col_pos, row_count, col_count, degree + 1)
              or find_grid(matrix, input_str, row_pos, col_pos - 1, row_count, col_count, degree + 1)
              or find_grid(matrix, input_str, row_pos, col_pos + 1, row_count, col_count, degree + 1))
        matrix[row_pos][col_pos] = temp
        return result
    else:
        return False

def solve(matrix, input_str, row_count, col_count):
    if len(input_str) > row_count * col_count:
        return False
    for row in range(row_count):
        for col in range(col_count):
            if matrix[row][col] == input_str[0]:
                if find_grid(matrix, input_str, row, col, row_count, col_count, 0):
                    return True
    return False

word_grid = ['pghsf', 'ykdgh', 'tkghi', 'hnsjs', 'ojfgh', 'nrtyu']
grid = [list(row) for row in word_grid]
print(solve(grid, 'python', 6, 5))

참고: 파이썬에서 문자열은 불변(immutable)이므로 문자열 행에 replace()를 호출해도 원본이 변경되지 않습니다. 따라서 위 코드처럼 각 행을 리스트(list)로 변환한 뒤 인덱스로 직접 값을 교체해야 방문 표시('#')와 복원이 실제로 동작합니다.

입력

['pghsf', 'ykdgh', 'tkghi', 'hnsjs', 'ojfgh', 'nrtyu'], 'python'

출력

True

시간 복잡도

각 시작점에서 최대 4방향으로 분기되며 단어 길이 L만큼 깊이 탐색하므로, 시간 복잡도는 O(R × C × 4^L)입니다. 여기서 R과 C는 각각 행과 열의 개수입니다. 공간 복잡도는 재귀 호출 스택을 포함해 O(L)입니다.