[백준알고리즘] 2178번: 미로 탐색 -Python

[백준알고리즘] 2178번: 미로 탐색 -Python

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

2178번: 미로 탐색

이번 문제는 반드시 (1, 1)에서 (N, M)으로 가는 것이기 때문에 길만 따라가면 돼서 간단하게 해결했다.

 

BFS로 문제를 풀었고, 이동한 각 지점에서 상하좌우를 큐에 넣어주었다. 큐에서 꺼낼 때 경곗값 검사를 진행해주었고, 해당 위치가 길이 맞는지 확인해주었다.

 

import sys
from collections import deque

def bfs():
    queue = deque([(1, 1, 0)])
    while queue:
        qi, qj, l = queue.popleft()
        if not 0<qi<=n or not 0<qj<=m or path[qi][qj] != 1:
            continue
        path[qi][qj] = path[qi][qj] + l
        l += 1
        queue.append((qi-1, qj, l))
        queue.append((qi, qj-1, l))
        queue.append((qi, qj+1, l))
        queue.append((qi+1, qj, l))

n, m = map(int, sys.stdin.readline().split())
path = [0]
for _ in range(n):
    path.append([0] + list(map(int, list(sys.stdin.readline().strip()))))
bfs()
sys.stdout.write(str(path[n][m]))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다