[백준] 2178 : 미로 탐색

문제

https://www.acmicpc.net/problem/2178

구조

• 이동할 네 가지 방향 정의
• 덱 생성
• while queue:
  현재 위치에서 4가지 방향으로 위치 확인
  위치가 범위 안에 있는지 조건 확인
  모든 조건이 통과되고 해당 값이 1이면 이동 가능
  이동해주면서 해당 미로의 값을 1씩 더해줌
  그리고 큐에 이동한 좌표를 넣어줌
• 마지막 노드에서 값을 리턴해줌

최단 경로

값을 갱신해주는 방식으로 최단 경로를 탐색해줄 수 있는 이유

• 갔다가 다시 되돌아 오는 경우 : 이미 지나왔던 값이 갱신되어 있어서 다시 못 돌아옴! => queue에 append되지 않아서 더이상 그곳을 기준으로 탐색하지 못함
• 아래로 갔다가 올라가서 도착하는 경우 : 이미 지나왔던 값이 갱신되어 있어서 다시 못 돌아옴

Queue에 append()해준다는 의미

이동한 좌표를 기준으로 또 상하좌우로 이동해준다는 뜻!
(append해주지 않는다는 의미는 이미 방문한 적이 있어서 값이 1이 아니게 되었다는 것이므로 더이상 이동한 좌표를 기준으로 상하좌우 이동을 안 해주겠다는 뜻!!

풀이

from collections import deque 

N, M = map(int, input().split())
miro = []
for _ in range(N):
    miro.append(list(map(int, input())))

# miro : [[1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1]

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

visited = [[False for _ in range(M)] for _ in range(N)]

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    num = 1
    while queue:
        x, y = queue.popleft()
        num = miro[x][y]
        # for i in  miro[x][y]: # k의 인접노드 for문 : 인접노드를 돈다기 보단, 상하좌우 -> 1이면 queue에 append
        #     if visited[i] == False:
        #         queue.append(i)
        #         visited[i] = True
        for i in range(4):
            a, b = x + dx[i], y + dy[i] # a, b는 이동할 경우의 점의 좌표
            if 0 <= a <= N-1 and 0 <= b <= M-1:
                if miro[a][b] == 1: # 이미 그 전에 방문했던 곳은 값이 갱신되어 있고 1이 아님! (그래서 최소경로 구할 수 있음)
                    queue.append((a,b))
                    miro[a][b] = num + 1
    return miro[N-1][M-1]
        
        
print(bfs(0,0))