[이코테] level2 BFS - 미로탈출 (python)

문제

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력

• 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력

첫째 줄에 최소 이동 칸의 개수를 출력한다.

입력 예시

5 6
101010
111111
000001
111111
111111

출력 예시

10

---

from collections import deque

n,m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
ans = 0

def in_range(x,y):
    if x>=0 and y>=0 and x<n and y<m:
        if graph[x][y] == 1:
            graph[x][y] = 0
            return True
        return False
    return False

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y):
    global ans
    queue = deque()
    # 최단거리를 구할 때 왜 bfs를 쓰는거지?
    queue.append((x,y))
    while queue:
        a,b = queue.pop()
        print(a,b)
        ans += 1
        if(a == n-1 and b == m-1):
            break
        for i,j in zip(dx,dy):
            nx = a + i
            ny = b + j
            if in_range(nx,ny):
                graph[nx][ny] = graph[a][b] + 1
                queue.append((nx,ny))

bfs(0,0)
print(ans)
print(graph[n-1][m-1])

처음 접근했을 때, queue를 pop 하는 경우를 세었다.

그러면 안되는게, 모든 너비들을 다 세는 경우기 때문이다.

 

따라서, 처음 도달한 즉 노드에 현재 값 + 1을 더해주고 append한다.

그리고 선입선출 큐니까 그 노드를 꺼내서 이동하고 +1해주니까

마지막 원소의 값은 +1+1 되어서 최단거리 값 남아있다.