📖접근
최단 거리 문제 -> BFS
칼을 먹고 나서는 어떻게 할 것인가?
칼을 먹고 나서 기존에 칼이 없을 때 방문 한 곳을 또 방문해도 된다.
이를 고려 안하면 틀립니다.
그래서 칼이 있는 위치에서 BFS를 다시 돌리면 문제를 풀 수 있다.
다만, 문제 관찰을 더 하면 좀 더 쉽고 빠르게 풀 수 있습니다.
칼을 먹고 나서는 벽을 고려 하지 않아도 됩니다. 그러면 최단 거리를 구할 때 반드시 BFS를 돌릴 이유가 있을 까요?
칼 위치 부터 도착지 까지 맨해튼 거리를 사용하는 건 어떨까요.
🐳배운 것
알고리즘은 문제를 푸는 방법!일 뿐이라는 것. 특정 알고리즘에 매몰되서
관찰을 소홀하지 말자. 이 문제의 경우 BFS만 생각할 시 맨허튼 거리라는 아이디어는 생각하지 못한다.
from collections import deque
def BFS(x, y):
global wx, wy
queue = deque()
queue.append((x, y))
visit[x][y] = 0
while queue:
x, y = queue.popleft()
# 칼 먹은 거 체크
if castle[x][y] == 2:
wx, wy = x, y
# n,m 도달시
if x == N-1 and y == M-1:
return visit[N-1][M-1]
for dx, dy in di:
nx, ny = dx + x, dy + y
if nx < 0 or ny < 0 or nx >= N or ny >= M: continue
if visit[nx][ny] != 1<<31: continue
if castle[nx][ny] == 1: continue
queue.append((nx, ny))
visit[nx][ny] = visit[x][y] + 1
# 성에 도달 못할 시
return 1<<31
N, M, T = map(int, input().split()) # T 는 제한 시간
castle = [list(map(int, input().rstrip().split())) for _ in range(N)]
visit = [[1<<31] * M for _ in range(N)]
di = [(1,0),(-1,0),(0,1),(0,-1)]
wx, wy = 1<<31, 1<<31
ans = BFS(0, 0)
if wx != 1<<31 and wy != 1<<31:
Manhattan = abs(N-1-wx)+abs(M-1-wy)+visit[wx][wy]
ans = min(ans, Manhattan)
print("Fail" if ans > T else ans)
'''
3 4 100
0 0 0 0
1 1 1 1
0 0 2 0
'''
'''
위와 같이 칼을 못먹는 예시가 았으므로
if castle[x][y] == 2:
wx, wy = x, y
칼을 먹을 수 있을 시 칼 위치를 체크해야합니다.
'''
/