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

문제 요약

미로를 탈출하는데 벽을 1개만큼은 뚫고 지나갈 수 있다는 것이다.

해결 전략

가장 중요한 핵심은 이것이라고 생각한다. 각 칸을 매우 큰 수로 초기화한 다음 이동할 곳이 현재 위치보다 더 큰 수라면 그곳으로 이동한다. 그러나 현재까지 뚫고 벽의 개수가 1이고 이동할 곳이 벽, 즉 1인 곳을 제외하고 말이다.
이때 경우가 3가지로 나뉘게 된다.

1)이동할 곳이 벽, 즉 1이고 현재까지 뚫고 온 벽의 개수가 0인 상황,
2)이동할 곳이 빈칸, 즉 0이고 현재까지 뚫고 온 벽의 개수가 1인 상황,
3)이동할 곳이 빈칸, 즉 0이고 현재까지 뚫고 온 벽의 개수가 0인 상황

어느 상황인지 판단한 뒤 출구까지 오게 되면 가장 짧은 길이를 출력하고,
모든 갈 수 있는 곳을 다 가보고(즉 큐가 빌 때까지) 했지만 출구로 끝나지 않았다면 -1을 출력해주면 끝인 문제이다.

코드 작성

import sys
from collections import deque
n,m=map(int,input().split())
hx,hy=map(int,input().split())
ex,ey=map(int,input().split())
graph,visit=[],[[[0,sys.maxsize] for __ in range(m)] for _ in range(n)]
for _ in range(n):graph.append(list(map(int,input().split())))
q=deque()
q.append((hx-1,hy-1))
visit[hx-1][hy-1][1]=0
dx,dy,ans=[-1,1,0,0],[0,0,-1,1],False
while q:
    x,y=q.popleft()
    if x==ex-1 and y==ey-1 and visit[x][y][1]<=1:
        ans=True
        print(visit[x][y][0])
        break
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if -1<nx<n and -1<ny<m and visit[x][y][1]<visit[nx][ny][1]:
            if graph[nx][ny]==1 and visit[x][y][1]==0:
                visit[nx][ny][0]=visit[x][y][0]+1
                visit[nx][ny][1]=1
                q.append((nx,ny))
            elif graph[nx][ny]==0 and visit[x][y][1]==1:
                visit[nx][ny][0]=visit[x][y][0]+1
                visit[nx][ny][1]=1
                q.append((nx,ny))
            elif graph[nx][ny]==0 and visit[x][y][1]==0:
                visit[nx][ny][0]=visit[x][y][0]+1
                visit[nx][ny][1]=0
                q.append((nx, ny))
if not ans:print(-1)