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

Python으로 격자에서 목표 지점까지 최단 경로 찾기 – BFS 알고리즘 구현

격자(grid) 안의 각 셀에는 'X', 'O', '*', '#'와 같은 다양한 기호가 들어 있으며, 각 기호는 서로 다른 의미를 가집니다.

  • '#'은 우리가 도달하고자 하는 목표(goal) 셀입니다.
  • 'O'는 자유롭게 이동할 수 있는 셀로, 이 셀을 경유해 목표 셀에 도달할 수 있습니다.
  • '*'는 현재 우리가 위치한 셀입니다.
  • 'X'는 막혀 있는 셀로, 통과할 수 없습니다.

이 문제의 목표는 격자 위에서 현재 위치('*')로부터 목표 셀('#')까지 도달하는 데 필요한 최소 이동 횟수를 구하는 것입니다. 만약 목표 셀에 도달할 수 없다면 -1을 반환해야 합니다. 격자는 프로그램의 입력으로 주어집니다.

예를 들어 입력이 아래와 같다면,

XXOX
XX*X
X#OX
XXXX

출력 결과는 2가 됩니다. 즉, 두 번의 이동만으로 목표 셀에 도달할 수 있습니다.

문제 해결 접근 방법

이 문제는 너비 우선 탐색(BFS)을 사용하면 효율적으로 해결할 수 있습니다. BFS는 시작 지점에서 인접한 셀들을 레벨(level) 단위로 확장해 나가기 때문에, 목표 셀에 처음 도달한 시점의 이동 횟수가 곧 최단 거리가 됩니다.

구체적인 해결 단계는 다음과 같습니다.

  • m := 격자의 행(row) 개수
  • n := 격자의 열(column) 개수
  • 이중 반복문으로 격자 전체를 순회하며 현재 위치 '*'의 좌표 (i, j)를 찾습니다.
  • ans := 0 (이동 횟수 초기화)
  • queue := 좌표 (i, j)를 담은 새로운 리스트 생성
  • grid[i][j] := "X" (시작 셀 방문 처리)
  • 큐가 비어 있지 않은 동안 다음을 반복합니다.
    • ans := ans + 1
    • newq := 새로운 리스트 생성
    • 큐에 있는 각 좌표 (i, j)에 대해 상하좌우 네 방향인 (i-1, j), (i, j-1), (i, j+1), (i+1, j)를 차례로 검사합니다.
    • 검사 중인 좌표 (ii, jj)가 격자 범위 내에 있고 해당 셀이 'X'가 아니라면,
      • 그 셀이 '#'이라면 ans를 반환합니다. (목표 도달)
      • 그렇지 않으면 newq의 끝에 (ii, jj)를 추가하고 grid[ii][jj] := "X"로 설정해 방문 처리합니다.
    • queue := newq 로 큐를 교체합니다.
  • 큐가 모두 비워질 때까지 목표에 도달하지 못했다면 -1을 반환합니다.

예제 구현

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

def solve(grid):
   m, n = len(grid), len(grid[0])
   for i in range(m):
      for j in range(n):
         if grid[i][j] == "*": break
      else: continue
      break
   ans = 0
   queue = [(i, j)]
   grid[i][j] = "X"
   while queue:
      ans += 1
      newq = []
      for i, j in queue:
         for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j):
            if 0 <= ii < m and 0 <= jj < n and grid[ii][jj] != "X":
               if grid[ii][jj] == "#": return ans
               newq.append((ii, jj))
               grid[ii][jj] = "X"
      queue = newq
   return -1

print(solve([['X', 'X', 'O', 'X'],['X', 'X', '*', 'X'],['X', '#',
'O', 'X'],['X', 'X', 'X', 'X']]))

입력

[['X', 'X', 'O', 'X'],
['X', 'X', '*', 'X'],
['X', '#', 'O', 'X'],
['X', 'X', 'X', 'X']]

출력

2