2022.03.29 [백준] (python 파이썬) 벽 부수고 이동하기

 

 

 

 

 

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

2206번: 벽 부수고 이동하기

---

풀이

이 문제는 최단 거리를 구하는 bfs문제이다. 여기서 한가지를 더 생각해야 한다.

1,1에서 n,m까지 이동하면서 벽을 하나 부수고 이동할 수 있다.

그래서 벽을 부수지 않았을 때, 벽을 부수었을 때, 총 2가지 경우를 생각해 주어야 한다.

그래서 기존의 2차원배열에서 2가지 경우를 더한 3차원배열을 만들어 문제를 해결해야한다. 

그래서 3차원 배열 visited을 만들었다. 여기서 wall이 0이면 벽을 부수지 않았을 때이고 1이면 벽을 부수었을 때이다. 

처음 3차원을 할 때, 생각하기 너무 어려웠다...

문제에서 총 2가지 경우가 있다. 그래서 두개의 다른 세계가 있다고 생각하면 쉽다. visited[x][y][0]은 벽을 부수지 않았을 때의 세계, visited[x][y][1]은 벽을 부수었을 때의 세계라고 생각한다.

그래서 같은 위치의 좌표라도 벽을 부수었을 때와 부수지 않았을 때를 모두 고려할 수 있다.

같은 위치일 때 벽을 부수었을때의 거리가 짧은 경우가 있다. 하지만 이 경우 다른 벽에 막혀 목표지점에 도달하지 못하면 해당 경로는 최단거리가 될 수 없다. 반대 상황으로 같은 위치일 때 벽을 부수지 않았을 때의 경우가 이동거리가 더 클수도 있다. 하지만 아직 하나의 벽을 부술 수 있기 때문에 목표지점에 도달할 수 있을수도 있다. 이 경우 최단거리가 될 수 있다. 

그래서 두 세계의 경우를 모두 생각하면서 문제를 해결할 수 있다.

또한 wall이 같을 때, 방문하지 않은 좌표만 확인한 이유는 만약 wall이 1이면 벽을 부수었을 때이고, 벽을 부수었을 때의 여러 경우중 먼저 해당 좌표에 도달한 경우가 같은 조건일 때 최단거리로 해당 좌표에 이동한 거리이기 때문에 방문하지 않은 좌표만 확인했다.

from collections import deque
 
n,m=map(int,input().split())
arr=[]
for _ in range(n):
    arr.append(list(map(int,input())))
 
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
 
dx=[1,-1,0,0]
dy=[0,0,1,-1]
 
def bfs():
    deq=deque()
    deq.append([0,0,0])
    visited[0][0][0]=1
 
    while deq:
        # wall이 0이면 벽을 부수지 않았을 때
        # 1이면 벽을 부수었을 
        x,y,wall=deq.popleft()
        if x==n-1 and y==m-1:
            return visited[x][y][wall]
 
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            # 이동햇을 때의 좌표가 범위 안에 있고, 해당 좌표에 방문하지 않았을 때
            if 0<=nx<n and 0<=ny<m and visited[nx][ny][wall]==0:
                # 벽이 아니고 길일 때
                if arr[nx][ny]==0:
                    deq.append([nx,ny,wall])
                    # 이전 위치에서 +1을 하여 이동거리를 저장함
                    visited[nx][ny][wall]=visited[x][y][wall]+1
                
                # 벽을 부수지 않았고, 해당 이동한 좌표가 벽일 경우
                if wall==0 and arr[nx][ny]==1:
                    deq.append([nx,ny,1])
                    visited[nx][ny][1]=visited[x][y][wall]+1
 
    return -1
 
print(bfs())