백준 / python / 2206. 벽 부수고 이동하기

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

 

문제 요약

0과 1로 표현된 지도에서 0은 길이고 1은 벽이다. 벽을 최대 한 번 부술 수 있을때, (0,0)->(N,M) 으로 최단 시간내에 가는 시간을 구하라.

 

 

풀이 요약

1. bfs 와 dp 로 푼다.

 

주의사항

각 이동 방향에 대해 n_bomb 은 항상 이전 상태로 초기화되어있어야한다. 

걸린 시간은 지도에 표기하면 편하다.

 

from sys import stdin, maxsize
from collections import deque

input = stdin.readline

N, M = map(int, input().split())
graph = []
score_map = [[[maxsize] * M for n in range(N)] for b in range(2)]
score_map[0][0][0] = 1
moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]

for n in range(N):
    graph.append(input())


def solve():
    # y, x, bomb
    q = deque([(0, 0, 0)])

    while q:
        y, x, bomb = q.popleft()

        if y == N - 1 and x == M - 1:
            return score_map[bomb][y][x]

        for dy, dx in moves:
            ny = y + dy
            nx = x + dx
            n_bomb = bomb
            if 0 <= ny < N and 0 <= nx < M:
                if graph[ny][nx] == "1":
                    if n_bomb:
                        continue
                    else:
                        n_bomb = 1
                if score_map[n_bomb][ny][nx] > score_map[bomb][y][x] + 1:
                    score_map[n_bomb][ny][nx] = score_map[bomb][y][x] + 1
                    q.append((ny, nx, n_bomb))

    return -1


print(solve())