[백준] 1261번_알고스팟

Study/알고리즘

[백준] 1261번_알고스팟

혤리 2020. 2. 28. 00:44

문제 링크 : https://www.acmicpc.net/problem/1261

1261번: 알고스팟

첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다.

www.acmicpc.net

from collections import deque
m,n = map(int,input().split())
maze = [list(map(int,input())) for _ in range(n)]

dx = (-1,1,0,0)
dy = (0,0,-1,1)
dist = [[-1]*m for _ in range(n)]
def bfs():
    q = deque()
    q.append((0,0))
    dist[0][0] = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx,ny = x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<m:
                if maze[nx][ny] == 0 and dist[nx][ny]==-1:
                    q.appendleft((nx,ny))
                    dist[nx][ny] = dist[x][y] 
                elif maze[nx][ny] == 1 and dist[nx][ny]==-1:
                    q.append((nx,ny))
                    dist[nx][ny] = dist[x][y] + 1
    return dist[n-1][m-1]
                    
print(bfs())