[백준 알고리즘] 2206. 벽부수고 이동하기

 

 

 

3차원 배열을 이용하지 않으면 쉽게 풀리지 않는 문제이다...

 

 

처음에는 그냥 2차원 배열에다가, 벽을 부순 여부를 crash 변수로 전달하게끔 했는데.. 잘 되지 않았다.

DFS로도 풀어봤는데 DFS는 답은 잘 구해졌는데 시간초과가 났다.

 

 

그래서 다른 분들의 풀이를 찾아봤는데 거진 다 3차원배열을 사용해 풀었다. 3차원 배열을 처음 사용해봐서 조금 낯설었는데, 풀어보니 확실히 편하다.. 2차원 배열 + 변수로 하려고 했던 것보다 편하다.

 

배열을 문제에 맞게 자유자재로 사용하는 것도 능력인 것 같다..!

 

from collections import deque


N, M = map(int, input().split())
map = [list(map(int, input())) for _ in range(N)]
visited = [[[0] * 2 for _ in range(M)] for _ in range(N)]
delta = [(1, 0), (0, 1), (0, -1), (-1, 0)]


Q = deque()
def BFS():
    ans = -1
    Q.append((0, 0, 0))
    visited[0][0][0] = 1
    while Q:
        r, c, crash = Q.popleft()
        if r == N-1 and c == M-1:
            ans = visited[N-1][M-1][crash]
            return ans
        for dt in range(4):
            nr = r + delta[dt][0]
            nc = c + delta[dt][1]
            if 0 <= nr < N and 0 <= nc < M:
                # 벽이 없고 방문하지 않았을 때
                if map[nr][nc] == 0 and visited[nr][nc][crash] == 0 :
                    visited[nr][nc][crash] = visited[r][c][crash] + 1
                    Q.append((nr, nc, crash))
                # 벽이 있고, 아직 부수지 않았을 때
                elif map[nr][nc] == 1 and crash == 0:
                    visited[nr][nc][1] = visited[r][c][0] + 1
                    Q.append((nr, nc, 1))
    return ans

print(BFS())