문제 - 미로 탈출
-
N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어서 이를 피해서 탈출해야한다.
-
동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 움직일 수 있다.
-
괴물이 있는 부분은 0, 없는 부분은 1로 표시된다.
-
탈출하기 위해서 움직여야 하는 최소 개수를 구하라.
제한 사항
- N, M은 (4 <= N, M <= 200) 이다.
코드
from collections import deque
def solution(n, m, graph):
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque()
queue.append((x, y))
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
if graph[nx][ny] == 0:
continue
if graph[nx][ny] == 1:
graph[nx][ny] = graph[x][y] + 1
queue.append((nx, ny))
return graph[n - 1][m - 1]
return bfs(0, 0)
if __name__ == "__main__":
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
print(solution(n, m, graph))
배운점
- 내 힘으로 풀 수 있을 때까지 풀어봐야겠다.
참고 문헌
>> Home