(Python) - BOJ(2206번) : 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

---

• 문제 : 

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

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

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

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

 

 

 

---

• 풀이 :

BFS로 구현 가능한 문제이다.

기본 아이디어는 벽이 없는 곳을 탐색하며 최단 경로로 목적지인 (N,M)에 도착하였을 때의 거리를 출력하는 것이지만, 

벽을 최대 한 개 부수고 이동할 수 있다는 조건 하나가 추가되어 꽤나 어려웠다.

 

일반 bfs 문제는 visited배열을 board와 같은 사이즈의 2차원 배열로 만들어서 방문 여부를 체크하지만 이 문제에서는 3차원 배열로 만들어 벽을 부수고 지났는지의 여부를 함께 체크해야 한다.

 

만약 이동하려는 칸이 벽이 아닐 경우 현재 visited[x][y][c]에 이전값 +1을 넣어주면 된다.

그러나 이동하려는 칸이 벽이고 visited의 z축에 해당하는 좌표값이 0일 경우 벽을 하나 부술 기회가 있는 것이므로 

벽을 부쉈다는 표시로 c를 1로 변경하여 queue에 넣어주면 된다.

 

 

 

---

• 소스코드 : 

from collections import deque

N, M = map(int, input().split())
graph = [list(map(int, input())) for _ in range(N)]
visited = [[[0,0] for _ in range(M)] for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]


if __name__ == "__main__":
    queue = deque()
    queue.append((0,0,0))
    visited[0][0][0] = 1

    while queue:
        x, y, c = queue.popleft()
        if x==N-1 and y==M-1:
            print(visited[x][y][c])
            exit()
        for i in range(4):
            ax = x + dx[i]
            ay = y + dy[i]
            if 0<= ax < N and 0 <= ay < M:
                if graph[ax][ay] == 0 and visited[ax][ay][c] == 0:
                    queue.append((ax, ay, c))
                    visited[ax][ay][c] = visited[x][y][c] + 1
                if graph[ax][ay] == 1 and c == 0:
                    queue.append((ax, ay, c + 1))
                    visited[ax][ay][c + 1] = visited[x][y][c] + 1
    print(-1)