벽 부수고 이동하기

출처 : 백준 #2206

시간 제한	메모리 제한
2초	192MB

---

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

---

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

---

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

---

입출력 예시

예제 입력 1

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1

15

---

예제 입력 2

4 4
0111
1111
1111
1110

예제 출력 2

-1

---

풀이

생각 및 풀이 설명

• BFS로 접근하였다.

• 처음에는 visited를 2차원 배열로 하여 계속 copy하여(재귀가 아니기때문에) 다음 큐에 넣고, 길이(d)를 1씩 증가시켜 나갔다.

  • crash의 초기값을 1로 설정하고 벽(1)을 만났을 때 부술 수 있는 count로 삼았다.
  • 이 풀이의 문제점은 배열을 copy함으로써 시간 복잡도가 증가하여 시간초과가 떴다.(slicing보다 deepcopy가 더 많은 시간이 소요된다. - 요소 뿐만아니라 모든 속성을 복사해야하므로)

• 아래 참고자료를 보고 다시 코드를 작성했다.
  참고자료

• visited를 3차원 배열로 만든다.

# visited
n = 6, m = 4
[[[0, 0], [0, 0], [0, 0], [0, 0]], 
[[0, 0], [0, 0], [0, 0], [0, 0]], 
[[0, 0], [0, 0], [0, 0], [0, 0]], 
[[0, 0], [0, 0], [0, 0], [0, 0]], 
[[0, 0], [0, 0], [0, 0], [0, 0]], 
[[0, 0], [0, 0], [0, 0], [0, 0]]]

• visited 안의 [0, 0] 중 첫번째 원소는 벽을 부수지 않을 때 거리를 기록한다. 두 번째 원소는 벽을 부쉈을 때 거리를 기록한다.
• 만약 matrix의 원소가 벽이 아니라면(0) visited[nx][ny][crash]에 값을 visited[x][y][crash]+1로 준다. (crash 횟수가 1이든 0이든 상관 없다.)
• 만약 matrix의 원소가 벽이라면(1) crash 횟수가 0일 때에만 visited[nx][ny][crash+1]에 값을 visited[x][y][crash]+1로 준다.
• visited를 3차원 배열로 만드는 것이 잘 이해가 되질 않았다.
• 사실 정답풀이가 처음 내가 생각한 풀이와 논리는 그리 다르지 않았지만, 시간 복잡도를 고려하지 않았기에 시간초과가 나올 수 밖에 없었다.
• 똑같은 bfs더라도 시간 복잡도가 천차만별일 수 있음을 깨닫게 되었다.

Python code (python3 - BFS)

# 백준 2206번 벽 부수고 이동하기
from sys import stdin
from collections import deque
import copy
input = stdin.readline

# n, m, matrix 입력받기
n, m = map(int, input().split())
matrix = []
one = []
final_one = []
for i in range(n):
    string = input().rstrip()
    temp = []
    for j in range(len(string)):
        s = int(string[j])
        temp.append(s)
        if s == 1:
            one.append((i, j))
    matrix.append(temp)

# 동 남 서 북
dx = [0, +1, 0, -1]
dy = [+1, 0, -1, 0]
start = (0, 0, 0)   # x = 0, y = 0, d = 1, crash = 0
def bfs(start):
    answer = int(1e9)
    global matrix
    # global visited
    visited = [[[0]*2 for _ in range(m)]for _ in range(n)]
    visited[0][0][0] = 1
    q = deque([start])
    while q:
        x, y, crash= q.popleft()
        if x == n-1 and y == m-1:
            answer = min(answer, visited[x][y][crash])               
            return answer
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if matrix[nx][ny] == 0 and visited[nx][ny][crash] == 0:
                    q.append((nx, ny, crash))
                    visited[nx][ny][crash] = visited[x][y][crash] + 1
                elif matrix[nx][ny] == 1 and crash == 0: 
                    q.append((nx, ny, crash+1))
                    visited[nx][ny][crash+1] = visited[x][y][crash] + 1   
    return False

result = bfs(start)
if result:
    print(result)
else:
    print(-1)