[BOJ] 2178. 미로탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

풀이

• queue를 사용한 BFS문제.

def solution(M, N, m):
    rs = 0
    visited = [[False for _ in range(N)] for _ in range(M)]
    queue = [[0, 0]]
    m[0][0] = 1
    # 상, 하, 좌, 우
    dx = [-1, 1, 0, 0] 
    dy = [0, 0, -1, 1]
    while queue:
        x, y = queue.pop(0)

        for idx in range(4):
            next_x = x + dx[idx]
            next_y = y + dy[idx]
            if 0 <= next_x < N and 0 <= next_y < M and m[next_x][next_y] == '1':
                if type(m[next_x][next_y]) == int:
                    m[next_x][next_y] = min(m[x][y]+1, m[next_x][next_y])
                else: m[next_x][next_y] = m[x][y]+1 
                queue.append([next_x, next_y])

    return m[N-1][M-1]

import sys
N,M = map(int, sys.stdin.readline().split(' '))


m = []
for _ in range(N):
    lst = [i for i in sys.stdin.readline().strip()]
    m.append(lst)
print(solution(M, N, m))