(Python/파이썬) - 백준(BOJ) 14442번 : 벽 부수고 이동하기 2

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

14442번: 벽 부수고 이동하기 2

---

• 문제 : 

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

 

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

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

 

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

 

 

 

---

• 풀이 :

bfs문제였습니다.

다만 벽을 부수고 이동하는 경우가 추가되어 까다로웠습니다.

 

문제 풀이입니다.

 

1. visited 배열을 3차원으로 선언하여 벽을 부수고 가는 경우와 벽을 부수지 않고 가는 경우를 나누어준다.

 

2. 4방향을 탐색하며 진행 가능한지 여부를 탐색한다. 만약 진행하려는 좌표가 벽인데 벽을 부순 개수가 K보다 작다면 벽을 부순 횟수를 1 증가시키고 큐에 넣는다.

 

3. 벽이 없는 빈 칸이라면 벽을 부순 횟수를 증가시키지 않고 큐에 넣는다.

 

4. R-1, C-1에 도착하면 목적지에 도착한 것이므로 이 때의 visited값을 출력한다.

 

 

 

---

• 소스코드 : 

import sys
from collections import deque
input = sys.stdin.readline

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

def bfs(start,K):
    visited = [[[-1] * C for _ in range(R)] for _ in range(K+1)]
    queue = deque()
    queue.append([0] + start)
    answer = R+C+1
    visited[0][start[0]][start[1]] = 0
    while queue:
        break_cnt, x, y = queue.popleft()
        if x == R-1 and y == C-1:
            return visited[break_cnt][x][y]+1
        for i in range(4):
            ax = x + dx[i]
            ay = y + dy[i]
            if 0 <= ax < R and 0 <= ay < C:
                if board[ax][ay] == 1 and break_cnt < K and visited[break_cnt + 1][ax][ay] == -1 :
                    queue.append([break_cnt+1,ax,ay])
                    visited[break_cnt+1][ax][ay] = visited[break_cnt][x][y] + 1
                elif board[ax][ay] == 0 and visited[break_cnt][ax][ay] == -1:
                    queue.append([break_cnt,ax,ay])
                    visited[break_cnt][ax][ay] = visited[break_cnt][x][y] + 1
    return -1
R,C,K = map(int,input().split())
board = [list(map(int,input().strip())) for _ in range(R)]

print(bfs([0,0],K))