[BOJ 백준] 2178번 미로 탐색 (python)

문제

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

2178번: 미로 탐색

접근

BFS를 통해 간단히 답을 구할 수 있다. 이때 임의의 칸(x, y)에 도착하는 가장 빠른 길이 아니라면 더이상 진행하지 않는 것이 시간을 줄이는 관건이다. 이는 visit 배열을 만들어 관리해 줄 수 있다.

코드

from collections import deque

n, m = map(int, input().split())
miro = []
for i in range(n):
    s = input()
    miro.append(s)

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visit = [[0 for col in range(110)] for row in range(110)]
dq = deque()
dq.append((0, 0))
visit[0][0] = 1

while True:
    if len(dq) == 0:
        break

    x, y = dq.popleft()
    for i in range(4):
        newx = dx[i] + x
        newy = dy[i] + y
        if newx >= n or newx < 0 or newy >= m or newy < 0:
            continue
        if miro[newx][newy] == "1":
            if visit[newx][newy] == 0:
                visit[newx][newy] = visit[x][y] + 1
                dq.append((newx, newy))
            elif visit[newx][newy] != 0 and visit[newx][newy] > visit[x][y] + 1:
                visit[newx][newy] = visit[x][y] + 1
                dq.append((newx, newy))

print(visit[n - 1][m - 1])

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study