[백준] 2206번 : 벽 부수고 이동하기

 

 

 

 

 

 

접근법

- 기존에 BFS를 푸는 방법과 동일하게 2차원 배열로 해결하는 방법으로 접근했다.

 

- 기존의 방법대로 한다면 matrix에서 1인 값들을 0으로 바꿔서 새 matrix를 만들고(이 경우 matrix의 크기만큼 for문이 돌아간다.) 그 matrix에서 BFS를 시행해서 결괏값을 얻어낸다.

 

- 배열의 크기가 최대 1,000,000인 것을 고려하지 못해서 결과적으로는 실패한 코드고 시간 초과가 발생하였다. 도저히 시간을 줄일 방법이 떠오르지 않아서 다른 분들의 코드를 참고하여 이해할 수 있었다. (Tistory 깨지고 부서져라)

 

- 다른 사람들은 대체로 3차원 배열로 접근을 해서 마지막 3차원에 벽의 깨진 상태를 1 혹은 0으로 보관하여 visit[row][col][0]이면 벽을 이미 깬 상태에서 이곳까지 접근하는 최소 비용, visit[row][col][1]이면 벽을 아직 깨지 않은 상태로 접근하는 최소 비용, 이런 방식으로 BFS를 누적해가는 것을 알 수 있었다.

 

- 기존과 방식은 동일하나 if문에 몇 가지 조건이 추가되었다. 기존에는 visit[n_row][n_col]이 1이면 갈 수 없기 때문에 돌아갔지만 여기서는 wall이 1이라면 즉, 아직 내가 벽을 부순 적이 없다면, 벽을 부순 것으로 계산하고 visit[n_row][n_col][0]에 visit[row][col][1]값 + 1을 넣어준다. 그 후 벽을 부쉈기 때문에 queue에 [n_row, n_col, 0]을 넣어줘서 그곳부터 다음 경로를 계산한다.

 

- matrix[n_row][n_col] == 0 즉, 그냥 길이면 기존의 BFS 방식과 동일하게 이동을 한다. 이때의 wall값은 변화가 없으므로 wall 변수 그대로 넣어주면 된다.

 

 

백준 사이트에 어떤 분이 DFS로 풀면 안 되는 이유를 적어놓으셔서 가져왔다.

1. 좌표의 상태를 유지하기 위해 매 방문마다 배열을 만들고 복사하는 작업은 비용이 너무 크다.

2. 1에 대한 대안으로 벽을 이미 부순 경우, 아직 부수지 않은 경우 두 가지만 전역에 배열을 선언한다.

3. 이 방법으로 dfs를 수행할 때 순환을 막기 위해서 지나온 배열은 다시 못지나가게 체크한다.

4. 다만, 현재 택한 길이 최적의 길이 아닐 수 있으므로 dfs수행이 종료된 시점에서 못지나가게 체크한 부분을 원상복구한다.

5. dfs는 깊이를 우선으로 탐색하기 때문에(최적이 나와도 최적인지 모르기 때문에) 전부 탐색해야 한다. => 시간초과

6. 백트래킹을 이용해 시간을 줄여볼 수 있지만 여전히 최악의 경우를 배제할 수 없다.

 

 

 

풀이

from collections import deque

dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

def BFS() :
    queue = deque()
    visit = [[[0] * 2 for i in range(M)] for _ in range(N)]
    queue.append([0, 0, 1])
    visit[0][0][1] = 1
    while queue :
        row, col, wall = queue.popleft()
        if row == N - 1 and col == M - 1 :
            return visit[row][col][wall]
        for i in range(4) :
            n_row = row + dx[i]
            n_col = col + dy[i]
            if 0 <= n_row < N and 0 <= n_col < M :
                if matrix[n_row][n_col] == 1 and wall == 1 :
                    visit[n_row][n_col][0] = visit[row][col][1] + 1
                    queue.append([n_row, n_col, 0])
                elif matrix[n_row][n_col] == 0 and visit[n_row][n_col][wall] == 0 :
                    visit[n_row][n_col][wall] = visit[row][col][wall] + 1
                    queue.append([n_row, n_col, wall])
    return -1

N, M = map(int, input().split())
matrix = list()
for _ in range(N) :
    matrix.append(list(map(int, input())))
print(BFS())

 

 

 

 

 

 

 

결과