[백준/2206/파이썬] 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

 

BFS/DFS에서 길을 찾아야하는데, 이번에는 벽을 부술 수 있게 되었다.

기존의 BFS/DFS과 다른 유형의 문제이다.

 

SOL)

"벽을 부순다는 개념을 어떻게 구현 해줄까." 가 key point인 문제이다. 

 

idea 1. 진짜, board에 벽을 1 → 0으로 바꿔주고, 다시 탐사를 진행한다. ⇒ 1000*1000 맵이기 때문에, 벽을 다 하나씩 바꾸고 bfs를 돌리면, BFS 시간복잡도 * 벽의 갯수 = NM * NM(최대) => NM^2  미뗫다. 안된다.

 

idea 2. 벽을 부수고(1개) 거리를 기록한 board, 벽을 부수지 않고 거리를 기록한 board 2개를 가지고, 먼저 도착하는 것의 거리를 출력해준다. 왜냐하면, 먼저 도착한다면 , N-1,M-1의 값이 큐에 빨리 추가가 될거기 때문

⇒ 이럴려면, 3차원 배열을 선언해줘서, 각각의 상태를 나타내어 주면 된다.

 

idea 3. DFS+ backtracking을 해준다.

=> backtracking 형식. 벽을 1번 부섰을 때 , dfs 진행. 하지만, 그 방법이 최솟값인지는 확실하지 않으니, 어쨋든 다 돌아 봐야함. 이 방법은 안됨. (NM^2)( 물론 backtracking으로 줄일 수 있겠지만, 줄일 수 있을지 없을지 확실하지 않기 때문에, 난 이걸 선택하지 않겠음)

 

제일 만만해 보이는 idea 2를 선택하겠음.

일단, BFS를 이용했으므로, 최단거리는 걱정없고,  벽을 부셨을때, 안부셨을 때, 상태를 메모리 공간을 더 활용해서 기록하는 아이디어 이므로, 코드의 가독성도 좋을거 같음.

import sys
from collections import deque
input = sys.stdin.readline

N,M = map(int,input().split())
board= [list(map(int,input().rstrip())) for _ in range(N)]
visited=[[[0]*M for _ in range(N)] for _ in range(2)]
dq = deque()
# 벽을 부수고 거리를 기록한 board
# 벽을 부수지 않고 거리를 기록한 board를 3차원의 형태로 나타내어준다.
dx=(1,0,-1,0)
dy=(0,1,0,-1)

def moving(wall,y,x):
    visited[wall][y][x] = 1
    dq.append((wall,y,x))
    while dq:
        wall,y,x = dq.popleft()
        if y== N-1 and x == M-1 :
            return visited[wall][y][x] # 어차피, 먼저 도착하는 친구가, 큐에 먼저 추가되기 때문에, 순서는 신경쓰지 않아도 된다.
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if (0<=ny<N and 0<=nx<M) and visited[wall][ny][nx] ==0:
                if board[ny][nx] == 0:
                    visited[wall][ny][nx] = visited[wall][y][x] +1
                    dq.append((wall,ny,nx))
                if board[ny][nx] == 1 and wall==0 :
                    visited[1][ny][nx] = visited[wall][y][x] +1
                    dq.append((1,ny,nx))
    return -1

print(moving(0,0,0))