[Python]1261. 알고스팟

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

1261번: 알고스팟

---

이 문제의 경우

주변이 '0' 이면 가중치가 0,

주변이 '1' 이면 가중치가 1이다.

 

따라서 일반적인 Queue를 사용한 BFS는 절대 풀 수 없고

Deque을 이용해서 가중치가 0 일땐 앞에다 추가하고 가중치가 1일땐 뒤에다가 추가해줘야 한다.

 

from collections import deque
 
dr = ((-1,0), (1,0), (0,-1), (0,1))
 
def bfs(st_y, st_x, ed_y, ed_x):
    queue = deque()
    queue.append((st_y, st_x))
    check[st_y][st_x] = True
    dist[st_y][st_x] = 0
    while queue:
        curr_y, curr_x = queue.popleft()
        for d in dr:
            next_y = curr_y + d[0]
            next_x = curr_x + d[1]
            if 0<=next_y<=ed_y and 0<=next_x<=ed_x:
                if check[next_y][next_x] == False:
                    if maze[next_y][next_x] == 0:
                        dist[next_y][next_x] = dist[curr_y][curr_x]
                        check[next_y][next_x] = True
                        queue.appendleft((next_y,next_x)) # 가중치가 0 이므로 앞에다 넣어준다.
 
                    else:
                        dist[next_y][next_x] = dist[curr_y][curr_x] + 1
                        check[next_y][next_x] = True
                        queue.append((next_y,next_x)) # 가중치가 1 이므로 뒤에다 넣어준다.
 
n, m = map(int, input().split())
maze = [list(map(int, input())) for _ in range(m)]
check = [[False]*n for _ in range(m)]
dist = [[-1]*n for _ in range(m)]
bfs(0,0,m-1,n-1)
print(dist[m-1][n-1])