BOJ 2178 - 미로 탐색

문제

백준 온라인 저지 - 2178번

풀이 과정

시작 지점에서 (N, M) 의 목표 지점에 도달하기 위한 최단 경로를 계산하는 BFS 문제입니다.
별다른 추가 조건 없이 기본적인 BFS 알고리즘을 구현해주면 됩니다.

코드

import sys
from collections import deque


N, M = list(map(int, sys.stdin.readline().split()))
board = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)]


dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(x, y):
    q = deque()
    visit = [[0]*M for _ in range(N)]

    q.append([x, y, 1])
    visit[x][y] = 1

    while q:
        x, y, cost = q.popleft()
        if x == N - 1 and y == M - 1:
            return cost

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < N and 0 <= ny < M:
                if not visit[nx][ny] and board[nx][ny]:
                    visit[nx][ny] = 1
                    q.append([nx, ny, cost + 1])


def solution():
    ans = bfs(0, 0)
    return ans


print(solution())