https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로www.acmicpc.net
가장 기본적인 방식
visited 2차원배열에, 한차원을 더 추가하여
벽을 부쉈는지를 판별한다.
만일 벽을 부쉈다면, 앞으로 벽을 부수지 못할 것이고,
벽을 부수지 않았다면, 벽을 부순 대신 벽을 부순 차원으로 넘어간다.
이렇게 가장 먼저 n-1,m-1에 도착한 요소를 찾아 +1 해주고 print(해주면된다.)
2차원까지는 머리가 돌아가는데, 3차원부터는 상당히 어지럽다.
주의할점: 파이썬에서 리스트 반복을 쓸 때는 거꾸로해줘야됨!!
import sysinput=sys.stdin.readlinefrom collections import dequearr=[]
move=[[-1,0],[1,0],[0,-1],[0,1]]n,m=map(int,input().split())if n==m==1:
print(1) exit()answer=1e+8for _ in range(n):
arr.append(list(map(int,input().strip())))def bfs(): global answer
visited=[[[0 for _ in range(m)]for _ in range(n)]for _ in range(2)] #벽여부, x,y
visited[0][0][0]=1 #지금있는곳 1로처리 visited[1][0][0]=1 #지금있는곳 1로처리
que=deque([[0,0,0]]) while que: w,cx,cy=que.popleft()
for dx,dy in move: nx,ny=cx+dx,cy+dy
if 0<=nx<n and 0<=ny<m and not visited[w][nx][ny]: #벗어나지 않고, 방문하지 않았다면
if nx==n-1 and ny==m-1: #정답조건이면
print(visited[w][cx][cy]+1) exit()
if arr[nx][ny]==1: #벽이라면 if not w: #안부순상태라면
visited[1][nx][ny]= visited[0][cx][cy]+1
que.append((1,nx,ny)) else:
continue #이미 부쉈다면 못부숨 else:
visited[w][nx][ny]=visited[w][cx][cy]+1 #벽아니라면 그냥 그상태로통과
que.append((w,nx,ny)) bfs()print(-1)