말이 되고픈 원숭이 문제를 풀었다면
아주 쉬운 문제
import sys
from collections import deque
def bfs():
visited[0][0][1] = 1
que = deque()
que.append([0, 0, 1])
while que:
x, y, k = que.popleft()
if x == N - 1 and y == M - 1:
return visited[x][y][k]
for i in range(len(direction)):
nx = x + direction[i][0]
ny = y + direction[i][1]
if 0 <= nx < N and 0 <= ny < M:
if k and mapData[nx][ny] and not visited[nx][ny][k - 1]:
que.append((nx, ny, k - 1))
visited[nx][ny][k - 1] = visited[x][y][k] + 1
if not mapData[nx][ny] and not visited[nx][ny][k]:
que.append((nx, ny, k))
visited[nx][ny][k] = visited[x][y][k] + 1
return -1
direction = [[-1, 0], [1, 0], [0, 1], [0, -1]]
N, M = map(int, input().split())
mapData = [[0] * M for _ in range(N)]
visited = [[[0 for i in range(2)] for i in range(M)] for i in range(N)]
for i in range(N):
temp = sys.stdin.readline()
for j in range(M):
mapData[i][j] = int(temp[j])
print(bfs())
'Algorithm > BFS, DFS' 카테고리의 다른 글
[백준] 12761번 돌다리 (0) | 2021.02.04 |
---|---|
[백준] 12851번 숨바꼭질 2 (0) | 2020.12.04 |
[백준] 7562번 나이트의 이동 (0) | 2020.09.23 |
[백준] 1600번 말이 되고픈 원숭이 (0) | 2020.09.23 |
[백준] 10451번 순열 사이클 (0) | 2020.09.21 |
댓글