[백준] 2178번. 미로탐색

문제

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

풀이

BFS로 접근하면 되는 문제였다.
시간복잡도를 줄이기 위해 deque랑 방문여부를 표시한 dictionary를 이용했다.

from collections import deque

#입력
n, m = map(int, input().split())
arr = [input() for _ in range(n)]

dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
visited = [[False] * m for _ in range(n)] # 방문 상태

queue = deque()
queue.append([0, 0])
visited[0][0] = True

distance = [[0] * m for _ in range(n)]
distance[0][0] = 1 #거리기록
while queue:
    curX, curY = queue.popleft()
    for dx, dy in dir:
        if 0 <= curX + dx < n and 0 <= curY + dy < m:
            if arr[curX+dx][curY+dy] == '1' and visited[curX+dx][curY+dy] == False:
                visited[curX+dx][curY+dy] = True
                distance[curX+dx][curY+dy] = distance[curX][curY] + 1
                queue.append([curX+dx, curY+dy])
                
print(distance[n-1][m-1])