[백준] 22944 죽음의 비 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/22944
• 🔑 BFS
  • 우산을 들고 있을 때, 안 들고 있을 때의 계산 처리
  • 우산을 들고 있으면 우산의 내구도만 내리고 다음 칸에 체력 저장
  • 우산을 안 들고 있으면 체력을 내리고 다음 칸에 체력 저장
  • 방문했던 곳은 현재 체력이 높을 때만 이동 (우산 때문에, 방문했던 곳의 체력보다 현재 체력이 더 많을 수 있어서)

 

import sys
from collections import deque
input = sys.stdin.readline

n, h, d = map(int, input().split())
MAP = [list(input()) for _ in range(n)]
start, end = [], []
visit = [[0] * n for _ in range(n)]

for i in range(n):
    if start and end:
        break
    for j in range(n):
        if MAP[i][j] == 'S':
            start = [i, j, h, 0, 0] 
            visit[i][j] = h
        elif MAP[i][j] == 'E':
            end = [i, j]

q = deque([start])

mx, my = [0, 0, 1, -1], [1, -1, 0, 0]

while q:
    x, y, hp, umbrella, dist = q.popleft()  # 시작 x, 시작 y, 체력, 우산 내구도, 거리

    for i in range(4):
        nx, ny = x + mx[i], y + my[i]

        if 0 <= nx < n and 0 <= ny < n:
            if MAP[nx][ny] == 'E':          # 안전 지대 도착
                print(dist+1)
                exit()
            
            next_hp = hp                    # 다음 칸에 넣을 체력
            next_umbrella = umbrella        # 다음 칸에 넣을 우산 내구도

            if MAP[nx][ny] == 'U':          # 다음 칸이 우산이면
                next_umbrella = d           # 우산 내구도를 넣어준다.
            
            if next_umbrella == 0:          # 우산을 들고있지 않으면
                next_hp -= 1                # 체력 깎는다.
            else:                           # 우산 들고있으면
                next_umbrella -= 1          # 우산 내구도 깎는다.

            if visit[nx][ny] < next_hp:     # 다음 칸에 저장된 체력보다 계산된 체력이 많으면 이동
                visit[nx][ny] = next_hp     
                q.append([nx, ny, next_hp, next_umbrella, dist + 1])

print(-1)