[백준] 14442번: 벽 부수고 이동하기 2

문제

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

분석

(1, 1)에서 (N, M) 까지 벽을 최대 K번 부수면서 도착할 때 최단 거리를 구하는 문제이다.

최단 거리를 구하는 문제이므로 일단 bfs 알고리즘을 생각할 수 있다.
visited 배열을 위치만 고려하지 않고 같은 위치더라도 남아있는 벽부수기 횟수가 다르다면 방문할 수 있게 했다. 따라서 visited는 3차원 배열로 격자 크기와 k+1(인덱스 계산 용이) 로 초기화했다.

처음 지점부터 최단 거리에 포함되기 때문에 처음 위치 x, y 그리고 최대 벽부수기 횟수(k) 에서 1로 초기화한다. (visited[x][y][z] = 1)

1. 방문하려는 곳이 1(벽)이고, z가 1이상(벽부수기 가능) 이고, 이미 방문한 곳이 아니라면,
   전 위치 + 남아있는 벽부수기 횟수를 고려한 visited배열에서 다음 방문할 visited배열에 +1을 해주고 큐에 append한다. (벽부수기 횟수는 1 빼준다.)
2. 방문하려는 곳이 0이고, 이미 방문한 곳이 아니라면,
   벽부수기 횟수는 유지한채 1번과 같은 동작을 한다.

bfs진행 중에 x, y가 n-1, m-1에 도달하면 즉시 visited[x][y][z]를 반환한다.
n-1, m-1에 도달하지 못하고 bfs가 끝나면 -1을 반환한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from collections import deque
MAX = 1000**2
n, m, k = map(int, input().split())
grid = [
    list(map(int, list(input().rstrip())))
    for _ in range(n)
]
visited = [[[0]*(k+1) for _ in range(m)] for _ in range(n)]
dxs = [0,1,0,-1]
dys = [1,0,-1,0]
def in_range(x, y):
    return 0<=x<n and 0<=y<m

def bfs(x, y, z):
    q = deque([(x, y, z)])
    visited[x][y][z] = 1
    while q:
        x, y, z = q.popleft()
        if (x, y) == (n-1, m-1):
            return visited[x][y][z]
        for dx, dy in zip(dxs, dys):
            nx, ny = x + dx, y + dy
            if in_range(nx, ny):
                if grid[nx][ny] == 1 and z and not visited[nx][ny][z-1]:
                    visited[nx][ny][z-1] = visited[x][y][z]+1
                    q.append((nx, ny, z-1))
                if grid[nx][ny] == 0 and not visited[nx][ny][z]:
                    visited[nx][ny][z] = visited[x][y][z]+1
                    q.append((nx, ny, z))
    return -1

print(bfs(0, 0, k))

이 문제는 python3로는 일반적으로 안 풀리는 듯하다. (python3 정답자 1명)

끝으로..

bfs응용 문제를 풀어봤는데, python3로 풀리지 않아서 생각보다 빡빡한 문제였다.