백준 2178번: 미로 탐색 (Python)

접근

문제 설명과 같이 BFS 알고리즘은 해당 위치까지 최단거리로 이동하는 특성이 있다.

예를 들어 첫 칸인 (0, 0)을 탐색할 때 BFS 알고리즘에 따라 현재칸을 기준으로 위, 아래, 왼쪽, 오른쪽 칸을 탐색하게 되는데, 이 칸들에 지금 칸 숫자에 1을 더한 2를 입력해준다. 이 다음 탐색에서는 주변 칸들에 3을 입력하는 식으로 진행하게 되면 마지막 칸에 최단거리를 표시하게 된다.

코드

import sys


def bfs(x, y):
    global cnt
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = [[x, y]]
    visited[x][y] = 1
    while q:
        now = q.pop(0)
        for i in range(4):
            nx = now[0] + dx[i]
            ny = now[1] + dy[i]
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1 and visited[nx][ny] == 0:
                q.append([nx, ny])
                visited[nx][ny] = visited[now[0]][now[1]] + 1


n, m = map(int, sys.stdin.readline().split())
maze = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
visited = [[0 for _ in range(m)] for __ in range(n)]
bfs(0, 0)
print(visited[n - 1][m - 1])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!