[py] 백준 - 알고스팟 (BFS)

문제

문제링크
현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

핵심

최소 거리를 구하는 문제이기 때문에 BFS를 이용한다.
각 방을 노드로, 방과 방 사이를 이동하는데 부숴야하는 벽의 수를 노드 간 이동 비용이라고 했을 때,벽이 없는 방(0)으로 이동하는데에는 비용이 0, 부숴야 하는 벽(1)으로 이동하는데에는 비용이 1 소모되는 0과 1의 비용을 가진 탐색이 된다.

비용이 0과 1로 나뉘어져있을때에는 deque를 사용해서 매 노드를 탐색할 때마다 갈 수 있는 노드에 대한 비용이 0이면 앞에, 1이면 뒤에 추가해주며 탐색을 이어나가면 된다.

그렇게 하면 비용이 적은 경로부터 우선적으로 탐색하고, 가장 적은 비용에 대한 탐색이 끝나고 나서야 비로소 더 큰 비용의 경로를 탐색하기 시작하기 때문에 벽을 최소한으로 부수고 이동하는 경로를 찾을 수 있게 된다.

우선탐색을 위해 queue.appendleft([drx, dry]) 이용하여 벽이있는경우를 마지막으로 두기

소스코드

import sys
from collections import deque
INF = 10987654321
N, M = map(int, sys.stdin.readline().split(" "))   # 4, 2
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
#방문 확인용 배열 
visited = [[-1 for _ in range(N)] for _ in range(M)]
#인풋으로 받을 배열
field = []
for _ in range(M):
    field.append(list(map(int, sys.stdin.readline().strip())))
queue = deque()
queue.append([0, 0])
visited[0][0] = 0
#print(visited , field)
while queue:
    x, y = queue.popleft()
    flag = 0
    for i in range(4):
        drx = x + dr[i]
        dry = y + dc[i]
        if 0 <= drx < M and dry >= 0 and dry < N and visited[drx][dry] == -1:
            #벽만나기
            if field[drx][dry] == 1:
                visited[drx][dry] = visited[x][y] + 1
                queue.append([drx, dry])
            elif field[drx][dry] == 0:
                queue.appendleft([drx, dry])  ##  ???
                visited[drx][dry] = visited[x][y]
                queue.append([drx, dry])
        # 도착한 경우
        if drx == M - 1 and dry == N - 1:
            print(visited[drx][dry])
            print(visited)
            flag = 1
            break
    if flag == 1:
        break