[ BOJ 2178 ] 미로 탐색(Python)

문제

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

[BOJ 2667. 벽을 부시고 이동하기] 문제에 뚜들겨 맞기 전에, 미리 풀면 좋을 것 같다. 😈
출발지에서 도착지까지 가장 짧은 칸 수로 이동하는 문제다.
bfs의 대표적인 문제니까 익숙해지면 좋을 것 같다!

문제 풀이

1. 현재 좌표 (i,j)가 이동할 수 있으면 현재 좌표를 key 값으로 그래프에 추가해주었다.
   ➣ graph[(i,j)]=[]

2. 현재 좌표의 상하좌우로 이동할 수 있으면, 현재 좌표를 key 값으로 갖게 추가해주었다.
   ➣ graph[(i,j)].append((nx,ny))

3. queue에 [(0,0),1] 을 추가해준다. 이 때 1은 이동한 횟수이다.
   ( 문제에서 이동횟수를 셀 때 출발지도 포함하기 때문에 1을 넣어주었다. )

4. queue에서 pop한 값이 현재 좌표가 도착지와 같으면 cnt를 return 한다.

5. 현재 좌표에서 이동할 수 있는 좌표들 중 방문하지 않은 좌표가 있으면 queue에 추가해준다. 방문 체크도 함께 해준다.
   ➣ queue.append([next_node,cnt+1])

코드

import sys
from collections import deque                                                           
input = sys.stdin.readline

n, m = map(int,input().rsplit())
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
graph, matrix = {}, []

for _ in range(n):
    row = input().rstrip()
    matrix.append(row)

for i,row in enumerate(matrix):
    for j,check in enumerate(row):
        if check == '1':
            graph[(i,j)]=[]
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                if 0 <= nx < n and 0 <= ny < m:
                        if matrix[nx][ny] == '1':
                            graph[(i,j)].append((nx,ny))

def bfs(graph,i,j):
    visit = [[0] * m for _ in range(n)]
    visit[0][0] = 1
    queue = deque()
    queue.append([(i,j),1])

    while queue:
        temp = queue.popleft()
        location, cnt = temp[0], temp[1]

        if location == (n-1,m-1):
            return cnt
            
        if location not in visit:
            x, y =location[0], location[1]
            visit[x][y] = 1

            if location in graph:
                next_nodes = list(graph[location])

                for next_node in next_nodes:
                    x, y =next_node[0], next_node[1]
                    if visit[x][y]== 0:
                        queue.append([next_node,cnt+1])
                        visit[x][y] = 1

    
print(bfs(graph,0,0))