백준 2206 벽부수고 이동하기

import sys
from collections import deque

input = sys.stdin.readline

N,M = map(int,input().split())
graph = [list(map(int,input().rstrip())) for _ in range(N)]
visited = [[[0]*2 for _ in range(M)] for _ in range(N)]    #각 층마다 방문여부 저장 리스트
queue = deque()

dr = [-1,1,0,0]    #상하좌우
dc = [0,0,-1,1]

def bfs(x,y,z):
    queue.append([x,y,z])
    visited[x][y][z] = 1    #시작점 포함이므로 1
    while queue:
        X,Y,Z = queue.popleft()

        if X == N-1 and Y == M-1:    #도착시에 print -> exit
            print(visited[X][Y][Z])
            exit(0)

        for i in range(4):
            NX = X+dr[i]
            NY = Y+dc[i]
            #범위안에있고
            if 0<=NX<N and 0<=NY<M:
                #벽이 아니고 방문한적이 없다면
                if graph[NX][NY] == 0 and visited[NX][NY][Z] == 0:
                    visited[NX][NY][Z] = visited[X][Y][Z] + 1
                    queue.append([NX,NY,Z])
                #벽이고 부술 수 있는 횟수가 남아있고 부순후에 지점을 방문한적이 없다면
                elif Z > 0 and visited[NX][NY][Z-1] == 0:
                    visited[NX][NY][Z-1] = visited[X][Y][Z] + 1    #부순 후 레이어에 방문횟수 증감
                    queue.append([NX,NY,Z-1])    #부순 레이어로 이동 -> (Z-1)
bfs(0,0,1)    #시작 x, 시작 y, 부술 수 있는 횟수
print(-1)

처음 시작 부분에서 마지막 인덱스까지 갈수있는 최단거리를 찾는 문제이다.

최단거리를 내는 중에 벽이 있다면 실행중 한번은 벽을 부술수 있는데

​

​

만약

0100

1110

1000

0000

0111

0000

0이 갈수있는 방향, 그리고 1이 벽이라 하고

0,0 인덱스에서 5,3 인덱스로 갈려하면 15번의 이동으로 최단경로를 낼수있는것이다.

0,1 인덱스의 1을 부수면 된다.

​

사실 이문제 아직 잘 이해못해서 이해 다하면 다시 수정함. ㅎ