[Boj] 미로찾기 2178(python)

문제링크 : https://www.acmicpc.net/problem/2178

구해야 할 목적이 미로에서 빠져나가는 최소한의 시간이므로, BFS를 선택함

시작지점 (0, 0)에서 BFS 함수 실행, 가야할 곳을 큐로 관리

BFS 함수를 실행하여 좌표를 하나씩 꺼내서 상하좌우 검사 후 조건에 맞는 좌표를 큐에 넣음

길이 1로 주어지므로, 다음 좌표의 값은 현재 좌표의 값를 더해주면 쉽게 구할 수 있음

최종적으로는 matrix[row-1][col-1]을 출력하면 됨

import sys
from collections import deque
sys.setrecursionlimit(10**8)

def BFS(start_row, start_col):
    to_visits = deque()
    start = [start_row, start_col]

    to_visits.append(start)
    while to_visits:
        current_row, current_col = to_visits.popleft()
        for i in range(4):
            next_row, next_col = current_row + dx[i], current_col+dy[i]
            if next_row < 0 or next_row >= row or next_col < 0 or next_col >= col:
                continue
            if 0 <= next_row < row and 0 <= next_col < col and matrix[next_row][next_col] == 1:
                matrix[next_row][next_col] += matrix[current_row][current_col]
                to_visits.append([next_row, next_col])

row, col = map(int, input().split())
matrix = []
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for _ in range(row):
    tmp = list(map(int, input()))
    matrix.append(tmp)

BFS(0, 0)
print(matrix[row-1][col-1])