[DFS/BFS] 백준 - 벽부수고 이동하기 2206번

벽부수고 이동하기 2206번

👌 문제 요약

벽을 한 개까지 부수고 이동하여야 할때 최단 경로를 구하는 프로그램을 구하여라.

😎 key point

벽을 1번 통과할 때랑 통과하지 않을 때의 최단 경로를 구하기 위해서는 벽을 한 번 통과했을 때의 거리와 벽을 통과하지 않았을 때의 거리를 모두 고려해야 한다는 점이다. (우선순위 큐나 다익스트라의 방법이 통하지 않는다.) 따라서 벽을 1번 통과할 때의 최단거리를 구하는 배열, 0번 통과할 때의 최단거리를 구하는 3차원 배열(2차원 배열 2개를 합치므로)을 만들어 먼저 도착지에 도달한 값을 구하는 방식으로 풀려고 한다.

💕 코드

from collections import deque

n, m = map(int, input().split())

graph = []

for _ in range(n):
    graph.append(list(map(int, input())))

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

def bfs():
    q = deque()
    q.append([0, 0, 0])
    # 벽을 한 번 통과했을 때의 거리와 벽을 통과하지 않았을 때의 거리를 모두 고려하는 3차원 배열 
    visited = [[[0]*2 for _ in range(m)] for _ in range(n)] 
    visited[0][0][0] = 1

    while q:
        y, x, z = q.popleft()  # z는 벽 통과 횟수를 나타내는 변수
        
        if y== n-1 and x== m-1: 
            return visited[y][x][z]

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= ny < n and 0 <= nx < m :
                
                if graph[ny][nx] == 0 and visited[ny][nx][z] == 0:
                    visited[ny][nx][z] = visited[y][x][z] + 1
                    q.append([ny, nx, z])
                if z == 0 and graph[ny][nx] == 1 and visited[ny][nx][z] == 0:
                    visited[ny][nx][1] = visited[y][x][0] + 1
                    q.append([ny, nx, 1])
    return -1

print(bfs())