[BFS,Deque] 백준-2206 벽 부수고 이동하기 골드2 (Python)

백준-2206 : 벽 부수고 이동하기

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

 

풀의

• 시작 점 부터 BFS 를 진행한다.
• BFS 를 진행하며 벽일 경우 벽을 아직 부수지 않았으면 벽을 부수고 진행한다.
  • 벽을 부순 유물를 3차원으로 관리

코드 (Python)

import sys
from collections import deque

read = sys.stdin.readline

n, m = map(int, read().split(" "))
matrix = [list(map(int, read().rstrip())) for _ in range(n)]
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]

# 상 하 좌 우
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def bfs(x, y, z):
    queue = deque()
    queue.append((x, y, z))
    visited[x][y][z] = 1

    while queue:
        x, y, z = queue.popleft()

        if x == n - 1 and y == m - 1:
            return visited[x][y][z]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if ny < 0 or ny >= m or nx < 0 or nx >= n:
                continue
            if matrix[nx][ny] == 1 and z == 0:
                visited[nx][ny][1] = visited[x][y][0] + 1
                queue.append((nx, ny, 1))
            elif matrix[nx][ny] == 0 and visited[nx][ny][z] == 0:
                visited[nx][ny][z] = visited[x][y][z] + 1
                queue.append((nx, ny, z))
    return -1


print(bfs(0, 0, 0))