백준 14442번 파이썬 문제풀이

문제

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을 출력한다.

문제풀이

이 문제는 부술 수 있는 벽의 갯수를 설정하고, 설정한 값보다 작거나 같게 벽을 부수고 이동했을 때 최소 시간이 걸리는 것을 찾는 문제이다.

처음에는 벽을 부순 상태에 대한 맵을 따로 만들지 않고, 방문 처리한 맵 하나만 만들어서 처리했다. 두번째 문제를 풀었을 때는 현재 부순 벽의 값을 표현할 수 있는 맵을 전부 만들어 접근했다. 첫번째와 두번째는 문제를 풀 때 소요되는 시간은 동일하지만, 첫번째 접근 방법은 메모리가 거의 0.5배 수준이 된다. 

방문 배열을 관리할 때는, 반드시 벽을 깨부순 상태를 관리를 해야한다. 이것을 고려하지 않을 경우, 아래와 같은 경우가 발생할 수 있기 때문이다. 

위 이미지를 살펴보면, 벽을 처음부터 깨고 온 경우에는 6만큼의 시간으로 올 수 있지만, 뺑 둘러올 경우 해당 위치에 도착하는데 필요한 시간은 10초이다. 그런데 실제로 답이 되는 것은 10초로 올 경우다. 

즉, 벽을 깨는 경우를 동일하게 간주할 경우, 최소의 시간만 넣게되면 위와 같은 경우에서 잘못 설정된 조건으로 고려되지 않는 경우가 발생한다. 따라서, 현재 벽을 깨부순 상태를 반드시 다르게 관찰해줘야 한다. 

 

접근방법1. 벽을 부순 횟수에 대한 맵을 전부 만들어 접근

먼저 공간복잡도가 가능한지 확인한다. (1,000 * 1,000 * 11 * 4) // (1024 * 1024) = 41.96MB로 메모리 제한에 걸리지 않는 것이 확인되었다. 따라서 위의 방법으로 접근해도 공간복잡도에서는 큰 문제가 없는 것이 확인이 된다. BFS는 아래 방식으로 접근했다. 

 

1. 시작지점을 큐에 넣는다. (현재 좌표, 현재 시간, 벽을 부순 횟수)
2. 큐에서 값을 뽑아온다.
3. 현재 노드 기준으로 갈 수 있는 노드를 탐색한다.
   3-1. 좌표 범위 안에 있다면 후속 진행한다.
   
   3-2. 현재 벽을 깬 개수 상태의 맵에서 다음 진행할 노드에 기록된 시간이 현재 시간 + 1 보다 큰 경우에 대해서만
   추가로 살펴본다. 현재 벽을 깬 개수 상태에 5라는 값이 적혀져 있고, 벽을 동일한 갯수만큼 부수고 왔을 때 값이 7이 된다면, 이 경우는 더 살펴볼 필요가 없다. 왜냐하면 앞으로 깰 수 있는 벽의 갯수가 똑같이 남아있기 때문에 더 늦게 돌아온 시간은 고려할 필요가 없어진다.
   
   3-3. 0을 만나게 되면, 큐에 값들을 넣는다.
   
   3-4. 1을 만나게 되면, 벽을 깨는 횟수가 한계를 넘는지 확인한다. 넘지 않는다면, 벽을 한번 더 깨었을 때 방문하는 다음 노드에 기록된 시간과 현재 시간을 비교해보고, 현재 시간 + 1 보다 크다면 que에 넣고, 그렇지 않다면 넣지 않는다.

import sys
from collections import deque


def bfs(n, m, k, my_list) :
    que = deque()

    # 방문 배열 초기화
    v = [[[9876543210 for _ in range(m)] for _ in range(n)] for _ in range(k+1)]
    que.append((0,0,1,0))
    v[0][0][0] = 1

    # BFS 시작
    while que :
        r, c, time, break_cnt = que.popleft()
        
        #도착지에 도착하면 현재 Time을 Return한다. 
        #다익스트라가 아니니 가장 먼저 도착하는 게 가장 빠르다.
        if r == n-1 and c == m-1 :
            return print(time)

        for rr, cc in tra_list :
            next_r, next_c = r + rr, c + cc

            #좌표 범위 내에서만 탐색
            if -1 < next_r < n and -1 < next_c < m :
                
                # 현재 상태의 다음 노드에 기록된 시간보다 현재 시간 + 1 이 더 작을 때만 추가 탐색
                # 이미 방문했는데, 더 빠르게 방문했던 적이 있다면 그 후의 탐색을 동일하게 진행했으니 불필요함.
                
                if v[break_cnt][next_r][next_c] > time + 1:
                    
                    # 0일 경우 추가 탐색한다.
                    # 앞에서 이미 지금 노드 시간에 대한 것은 고려가 끝이 남.
                    if my_list[next_r][next_c] == '0'  :
                        v[break_cnt][next_r][next_c] = time + 1
                        que.append((next_r, next_c, time +1 , break_cnt))

                    # 1일 경우, 벽을 더 부술 수 있는지 먼저 확인한다.
                    # 더 부술 수 있다면, 더 부숴서 다음 노드를 방문하는 시간이 최적인지 확인한다.
                    # 최적이라면 que에 또 넣는다.
                    elif my_list[next_r][next_c] == '1' and break_cnt + 1 <= k :
                        if v[break_cnt + 1 ][next_r][next_c] > time + 1 :
                            v[break_cnt + 1 ][next_r][next_c] = time + 1
                            que.append((next_r, next_c, time + 1 , break_cnt + 1 ))


    return print(-1)



#변수 입력 받기
n, m, k = map(int,sys.stdin.readline().split())
my_list = []
for ___ in range(n) :
    my_list.append(str(sys.stdin.readline().rstrip()))

tra_list = [[1,0],[0,1],[-1,0],[0,-1]]
bfs(n,m,k,my_list)