[BFS] 백준 2178번 미로 탐색 with Python3

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

2178번: 미로 탐색

문제

 

내 풀이

from collections import deque

n, m = map(int, input().split())

# maze = [list(input()) for _ in range(n)]
maze = []
for i in range(n):
    maze.append(list(map(int, input())))
visited = [[0] * (m) for _ in range(n)]

# 상 우 하 좌
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
count = 0


def bfs(r, c):
    que = deque([])
    que.append([r, c])
    visited[r][c] = 1

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

            if (0 <= nx < n) and (0 <= ny < m) and visited[nx][ny] != 1 and maze[nx][ny] != 0:

                visited[nx][ny] = 1
                que.append([nx, ny])
                maze[nx][ny] = maze[x][y] + 1


bfs(0, 0)
print(maze[n-1][m-1])

해설

여태 풀어봤던 문제와 유사점이 많은 다운그레이드 버젼이라고 생각해 처음엔 섯불리 dfs 알고리즘을 사용했다가 최소 거리 개수를 세는 방법에서 막혔다. 그 잔재는 count = 0 으로 확인 할 수있다.

 

bfs는 간선 비용이 같을 때 최단거리를 알려줄 수 있는 알고리즘이기에 이를 사용해야했다.

 

상우하좌 식으로 x , y 좌표를 바꿔주는 알고리즘은 안전영역에서 따왔다.

각종 조건들로 이상한데로 가지 않게 제한해주었다.

 

가장 중요한 코드는 아래서 세번쨰 줄인데, 다음 좌표의 값에 이전 좌표 값을 추가해주는 것이다. 이를 통해 문제에서 원하는 위치가 아니더라도 방문 할 수 있는 좌표라면 어디든 해당 좌표에 원소에 최단 거리가 저장되어있다. !