백준 2178번-BFS solution (Python)

BFS 연습으로 좋은 문제이다.

풀이

from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
matrix = [input().rstrip() for _ in range(N)]
visited = [[0] * M for _ in range(N)]
dx = [-1, 1, 0, 0] # 좌 우 하 상 좌표
dy = [0, 0, -1, 1] # 좌 우 하 상 좌표

q = [(0, 0)] # BFS 탐색의 다음 가능 (경로)좌표가 저장할 리스트
visited[0][0] = 1 # 경로 길이 counnt
while q: # 더 이상 갈 경로가 없을 때까지
    # print(q) # for checking
    x, y = q.pop(0)
    
    if (x == N-1) and (y == M-1): # 도착하면 경로길이(visited값) 출력
        print(visited[x][y])
        break
    
    for i in range(4): # 상하좌우 네 가지 경우의 수를 위한 반복문
        nx = x + dx[i] # 움직였을 때 x좌표
        ny = y + dy[i] # 움직였을 때 y좌표
        if (0<=nx<N) and (0<=ny<M):
            if visited[nx][ny] == 0 and matrix[nx][ny] == '1':
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))

문제 출처 백준2178번