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

문제

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

 

문제 풀이

 앞서 다룬 벽 부수고 이동하기 문제에서 경우의 수가 K로 추가된 문제이다. 해당 문제에서는 입력되는 K에 따라 벽을 부 술 수 있는 횟수가 증가하게 된다. 따라서 경우의 수는 벽을 부순 횟수가 (0, 1, ... K)로 증가된 문제이다. 벽 부수고 이동하기 코드에서 K에 대한 경우의 수를 추가해주면 해결 할 수 있다. (단, PyPy3로 제출하여야 시간 내에 통과할 수 있다.)

 

코드

from sys import stdin
from collections import deque


def visitable(x, y, w):
    return 0 <= x < n and 0 <= y < m and not visited[x][y][w]


def bfs(start):
    q = deque([start])
    dirs = ((-1, 0), (0, 1), (1, 0), (0, -1))

    while q:
        cur_x, cur_y, wall = q.popleft()
        dist = visited[cur_x][cur_y][wall] + 1

        if [cur_x, cur_y] == [n - 1, m - 1]:
            return visited[cur_x][cur_y][wall]

        for x, y in dirs:
            next_x, next_y = cur_x + x, cur_y + y
            if visitable(next_x, next_y, wall):
                if not graph[next_x][next_y]:
                    visited[next_x][next_y][wall] = dist
                    q.append((next_x, next_y, wall))
                elif wall < k:
                    visited[next_x][next_y][wall + 1] = dist
                    q.append((next_x, next_y, wall + 1))

    return -1


if __name__ == '__main__':
    n, m, k = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().strip())) for _ in range(n)]
    visited = [[[0] * (k + 1) for _ in range(m)] for _ in range(n)]
    visited[0][0] = [1] * (k + 1)
    print(bfs((0, 0, 0)))