2차원 격자(grid)로 표현된 미로가 있다고 가정해 보겠습니다. 여기서 0은 빈 공간을, 1은 벽을 의미합니다. 우리는 grid[0][0], 즉 왼쪽 상단에서 출발하여 격자의 오른쪽 하단 모서리까지 이동해야 하며, 이때 지나가야 하는 칸의 최소 개수를 구하는 것이 목표입니다. 만약 어떤 경로로도 도달할 수 없다면 -1을 반환합니다.
예를 들어 다음과 같은 입력이 주어졌다고 해보겠습니다.
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 1 | 0 | 0 |
이 경우 출력은 5가 됩니다.
문제 해결 접근 방법
이 문제는 BFS(너비 우선 탐색)를 사용하면 효율적으로 해결할 수 있습니다. BFS는 가중치가 없는 그래프에서 시작점부터 목적지까지의 최단 경로를 찾는 데 가장 적합한 알고리즘이기 때문입니다. 각 칸은 상하좌우 네 방향으로만 이동할 수 있으며, 이미 방문한 칸은 다시 방문하지 않도록 표시해 무한 루프를 방지합니다.
구체적인 단계는 다음과 같습니다.
- R := 격자의 행(row) 개수, C := 격자의 열(column) 개수로 설정합니다.
- A[0][0]이 0이라면 큐 q를 [(0, 0, 1)]로 초기화하고, 그렇지 않으면 빈 리스트로 초기화합니다. 여기서 세 번째 값은 현재까지 지나온 칸 수를 의미합니다.
- 시작 칸 A[0][0]을 방문 처리(1로 변경)합니다.
- 큐에서 (r, c, d)를 하나씩 꺼내며 다음을 반복합니다.
- (r, c)가 (R − 1, C − 1), 즉 오른쪽 하단 모서리와 같다면 d를 반환합니다.
- 그렇지 않으면 상하좌우 네 방향의 인접 칸 (x, y)를 차례로 확인합니다.
- (x, y)가 격자 범위 내에 있고 A[x][y]가 0(빈 공간)이라면, 해당 칸을 방문 처리하고 (x, y, d + 1)을 큐의 끝에 추가합니다.
- 큐가 모두 비워질 때까지 목적지에 도달하지 못했다면 -1을 반환합니다.
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드
class Solution:
def solve(self, A):
R, C = len(A), len(A[0])
q = [(0, 0, 1)] if not A[0][0] else []
A[0][0] = 1
for r, c, d in q:
if (r, c) == (R − 1, C − 1):
return d
for x, y in [(r + 1, c), (r − 1, c), (r, c + 1), (r, c − 1)]:
if 0 <= x < R and 0 <= y < C and A[x][y] == 0:
A[x][y] = 1
q.append((x, y, d + 1))
return −1
ob = Solution()
grid = [
[0, 0, 0],
[1, 0, 0],
[1, 0, 0]
]
print(ob.solve(grid))
입력
grid = [ [0, 0, 0], [1, 0, 0], [1, 0, 0] ]
출력
5
동작 원리 살펴보기
위 예제에서 BFS는 (0, 0)에서 출발하여 인접한 빈 칸들을 차례대로 탐색합니다. 첫 번째 열의 아래쪽 두 칸은 벽(1)이므로 통과할 수 없고, 대신 오른쪽 경로를 따라 (0, 0) → (0, 1) → (0, 2) → (1, 2) → (2, 2) 순서로 이동하게 됩니다. 총 5개의 칸을 거쳐 오른쪽 하단에 도달하므로 결과값은 5가 됩니다.
BFS는 같은 거리에 있는 모든 칸을 동시에 탐색하기 때문에, 목적지에 처음 도달했을 때의 거리 값이 곧 최소 이동 칸 수가 됩니다. 시간 복잡도는 O(R × C)로, 격자의 모든 칸을 최대 한 번씩만 방문하므로 매우 효율적입니다.