[python]🔥2206번 벽 부수고 이동하기

이 문제에서 가장 어려웠던 부분은 방문배열을 어떻게 만드냐였다.

평소처럼 이차원 배열로 방문 여부를 벽 부순 상태 상관없이 저장을 하니 틀렸다.

 

반례 중에 아래와 같은 것이 있다.

5 5
00100
00000
10010
00101
00010

 통일된 방문여부배열은 벽을 부수면서 간 그래프가 방문을 먼저 해버려서 벽을 안 부순(우회해서 간) 그래프들이 방문여부에 가로막혀

목표 정점에 도달 할 수가 없다.

 

그래서 벽을 부쉈고 안 부쉈고에 따라서 방문 여부를 따로 저장을 한 것이었다.

그래야 벽을 안 부순 그래프들은 벽을 부순 그래프들 영향 안 받고 정점들을 지나갈 수 있으니 말이다.

import sys
from collections import deque
que = deque()
input = sys.stdin.readline
row,clmn = map(int,input().split())
stg = []
visit = [[[0 for i in range(clmn)] for j in range(row)] for k in range(2)]
for i in range(row):
    stg.append(input().strip())
que.append((0,0,1,0))
visit[0][0][0] = 1
if row == 1 and clmn ==1:
    print(1)
    exit(0)
while que:
    cur = que.popleft()
    for i in [(cur[0]+1,cur[1]),(cur[0],cur[1]-1),(cur[0],cur[1]+1),
            (cur[0]-1,cur[1])]:
        if 0<=i[0]<row and 0<=i[1]<clmn:
            if i[0] == row-1 and i[1] == clmn-1:
                print(cur[2]+1)
                exit(0)
            elif stg[i[0]][i[1]] == '0':
                if not cur[3] and not visit[0][i[0]][i[1]]:
                    que.append((i[0],i[1],cur[2]+1,cur[3]))
                    visit[0][i[0]][i[1]] = 1
                elif cur[3] and not visit[1][i[0]][i[1]]:
                    que.append((i[0],i[1],cur[2]+1,cur[3]))
                    visit[1][i[0]][i[1]] = 1
            elif stg[i[0]][i[1]] == '1':
                    if not cur[3] and not visit[0][i[0]][i[1]]:
                        que.append((i[0],i[1],cur[2]+1,cur[3]+1))
                        visit[0][i[0]][i[1]] = 1
print(-1)