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

BFS

문제 : 벽 부수고 이동하기2

BFS 문제 입니다 .
벽 부수고 이동하기 문제와 다른점은
만약에 이동하는 도중에 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 K개 까지 부수고 이동하여도 된다.
부술 수 있는 벽의 개수가 k 개라는 것입니다.
이것말고는 1번 문제와 동일합니다.

조건은 다음과 같이 두가지 입니다.
1. 벽이 있고, 벽을 부술 수 있으며, 다음 칸에 방문한 적이 없다.
2. 벽이 없고, 다음 칸에 방문한 적이 없다.

import sys
from collections import deque
input = sys.stdin.readline
n, m, k = map(int, input().split())
lst = [list(map(int, sys.stdin.readline().rstrip())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(a, b, visit):
	q = deque()
	q.append((a, b, visit))
	visited = [[[0]*(k+1) for _ in range(m)] for _ in range(n)]
	visited[0][0][k] = 1
	while q:
		x, y, v = q.popleft()
		if x == n-1 and y == m-1:
			return visited[x][y][v]
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			if nx < 0 or ny < 0 or nx >= n or ny >= m:
				continue
            # 벽이 있고, 부술 수 있으며, 다음 칸이 방문한 적이 없다.
			if lst[nx][ny] == 1 and v > 0 and visited[nx][ny][v-1] == 0:
				visited[nx][ny][v-1] = visited[x][y][v] + 1
				q.append((nx, ny, v-1))
			# 벽이 없고, 다음 칸이 방문한 적이 없다.
			if lst[nx][ny] == 0 and visited[nx][ny][v] == 0:
				visited[nx][ny][v] = visited[x][y][v] + 1
				q.append((nx, ny, v))
	return -1
print(bfs(0, 0, k))

python3으로 하면 시간초과가 나고 pypy3으로 해야 시간초과 없이 통과 할 수있습니다.