[BOJ1261 알고스팟] BFS (Python)

문제조건

벽이 있으면 뚫고 이동, 벽이 없으면 그냥 이동한다.

핵심개념

• 가중치(부수는 벽의 개수)는 벽이 있느냐 마느냐에 따라 0이거나 1이다.
• 가중치가 1이면 deque의 왼쪽, 0이면 deque의 오른쪽을 사용한다. (2개의 큐인 것처럼 활용)

코드

from collections import deque

n, m = map(int, input().split())
miro = [list(map(int, input())) for _ in range(m)]
check = [[False] * n for _ in range(m)]
dist = [[-1] * n for _ in range(m)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 처음 위치
q = deque()
q.append((0, 0))
check[0][0] = True
# 부순 벽의 개수
dist[0][0] = 0

while q:
    # 벽을 안 부수는 큐를 먼저 꺼낸다. (최소를 구해야 하니까)
    x, y = q.popleft()

    # 위, 아래, 왼, 오 이동하면서 탐색 시작
    for k in range(4):
        nx, ny = x + dx[k], y + dy[k]

        # 미로 밖을 넘어가는지 안넘어가는지 확인
        if 0 <= nx < m and 0 <= ny < n:
            # 벽이 있는 경우 (벽을 부순다), deque의 오른쪽 이용
            if miro[nx][ny] == 1 and check[nx][ny] == False:
                q.append((nx, ny))
                check[nx][ny] = True
                dist[nx][ny] = dist[x][y] + 1

            # 벽이 없는 경우 (벽을 안 부순다), deque의 왼쪽 이용
            if miro[nx][ny] == 0 and check[nx][ny] == False:
                q.appendleft((nx, ny))
                check[nx][ny] = True
                dist[nx][ny] = dist[x][y]

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