[백준 14442번] 파이썬 - 벽 부수고 이동하기 2

백준 14442 - 벽 부수고 이동하기2

시간 제한 2초, 메모리 제한 512MB

# 조건

• N×M의 행렬로 표현되는 맵이 있다.
• 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.
• 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다.
• 최단 경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
• 만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.
• 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
• 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

• 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다.
• 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.
• (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

• 첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

# 접근 방법

• BFS를 이용하여 풀어준다.
• VISITED 배열은 [[K+1] * M for _ in range(N)]로 생성해준다.
  • visited[i][j]는 현재 좌표까지 최단 거리로 올 때 부순 벽의 개수로 기록해준다.
• 또한 q에는 (si, sj, cnt) 를 인자로 넘겨주며 현재 좌표와, 지금까지의 최단 거리를 기록해준다.
• bfs이므로 부순 벽의 개수와 상관없이 도착지까지 최단 거리는 벽을 부순 횟수와 상관없이 보장된다.
• 따라서, 상하좌우를 탐색하며 범위 내이고 visited[si][sj] + arr[ni][nj] < visited[ni][nj] 라면 visited[ni][nj] = visited[si][sj] + arr[ni][nj] 로 기록해주고 q에 담아준다.
  • 즉, 현재까지 부순 벽의 개수 + 다음 좌표에서의 값 (벽이라면 1, 아니면 0)이 visited에 기록된 현재까지 부순 벽의 개수보다 작다면, 계속 탐색하는 것이다.
  • 벽을 적게 부순 경우만 새로운 경로이기 때문에!!

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs():  
    q = deque()  
    q.append((0, 0, 1))  
    visited[0][0] = 0  
    while q:  
        si, sj, cnt = q.popleft()  
        if (si, sj) == (N-1, M-1):  
            print(cnt)  
            return  
        for d in range(4):  
            ni, nj = si+di[d], sj+dj[d]  
            if in_range(ni,nj) and visited[si][sj] + arr[ni][nj] < visited[ni][nj]:  
                # 현재 좌표까지 부수고 온 벽 + 다음 좌표의 값 (벽이면 1, 빈 공간이면 0)이 현재 기록된 부순 벽의 개수보다 작다면  
                # q에 넣어주기                
                visited[ni][nj] = visited[si][sj] + arr[ni][nj]  
                q.append((ni, nj, cnt+1))  
    print(-1)  

def in_range(ni, nj):  
    if 0<=ni<N and 0<=nj<M:  
        return 1  
    return 0  

N, M, K = map(int, input().split())  

arr = [list(map(int, list(input().strip()))) for _ in range(N)]  
di, dj = [-1, 0, 1, 0], [0, 1, 0, -1]  
# visited[i][j]는 현재 좌표까지 최단 거리로 오면서 부순 벽의 개수  
visited = [[K+1]*M for _ in range(N)]  
bfs()