벽 부수고 이동하기

2206번: 벽 부수고 이동하기

🤔생각해보기

처음 떠올린 방법은, visited 와 똑같은 crashed 라는 배열을 만들어놓고 벽을 뚫었을 때 체크하는 방법과 3차원 배열을 활용해서 풀어보는 방법이다. 개인적으로는 2차원 배열도 머리가 복잡해져서 꺼리게 되는지라 3차원 배열 활용은 뒤로 미루고 crashed 라는 새로운 배열을 만들어놓고 활용해보려 했는데, 잘 안풀리고 오히려 더 복잡해져서 결국 1시간이나 더 써서 3차원 배열로 풀었다.

(처음부터 그냥 곱게 3차원 쓸걸...)

3차원 배열을 활용해야하는 이유는 벽을 뚫었는지 여부를 같이 저장해야하기 때문이다.

한 번 넘어갔다가 다시 넘어오는 코드를 만들지 않고 목적지에 도달했을 때 위 아래 그래프 중 더 큰 값을 리턴해주자.

성공

from collections import deque

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


def bfs():
    visited[0][0][0] = 1
    queue = deque([[0, 0, 0]])

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

    while queue:
        w, x, y = queue.popleft()
        if x == N - 1 and y == M - 1:
            return max(visited[0][x][y], visited[1][x][y])

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < M:
                if visited[w][nx][ny] == 0 and graph[nx][ny] != 1:
                    visited[w][nx][ny] = visited[w][x][y] + 1
                    queue.append([w, nx, ny])

                # 벽을 뚫은 적이 없는 상태에서 벽을 만난다면 겹쳐져 있는 3차원 배열의 다른 쪽으로 넘어가자.
                elif visited[1][nx][ny] == 0 and graph[nx][ny] == 1 and w == 0:
                    visited[1][nx][ny] = visited[0][x][y] + 1
                    queue.append([1, nx, ny])
    return -1


print(bfs())