[BOJ/백준] 22944 죽음의 비 파이썬

문제 링크 : https://www.acmicpc.net/problem/22944

22944번: 죽음의 비

 

나는 BFS로 풀었고 방문체크는 해당 칸을 방문했을 때의 체력을 기록했다. 그래서 다음번에 다시 방문했을 때 해당 칸보다 체력이 높아야 이동이 가능하게 했다.

더 낮은데 해당 칸으로 이동해봐야 기존의 방문했을 때보다 적게 가기 때문이다.

 

BFS 진행시 범위 안에 들어왔을 때 조건들을 체크한다.

만약 E점이라면 종료한다.

 

아니라면

다음 점이 우산이라면 현재 내구도를 d로 바꾼다.

 

다음 현재 내구도가 0이라면 체력 -1 아니라면 내구도 -1을 하는데 이때 체력이 0이라면 넘어간다.

마지막으로 방문체크하고 큐에 넣는다.

 

from sys import stdin
from collections import deque

input = stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]

n,h,d = map(int, input().split())
board = []

sx=sy=-1
for x in range(n):
    board.append(list(input().strip()))
    if sx==-1:
        for y in range(n):
            if board[x][y] == 'S':
                sx,sy = x,y

def solv():
    visited = [[0]*n for _ in range(n)]
    q = deque([(sx,sy,h,0,0)])
    visited[sx][sy] = h

    while q:
        x,y,now_h,now_d,cnt = q.pop()

        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]

            if point_validator(nx,ny):
                if board[nx][ny] == 'E':
                    print(cnt+1)
                    return
                nxt_h = now_h
                nxt_d = now_d

                if board[nx][ny] == 'U':
                    nxt_d = d

                if nxt_d == 0:
                    nxt_h -= 1
                else:
                    nxt_d -= 1

                if nxt_h == 0:
                    continue

                if visited[nx][ny] < nxt_h:
                    visited[nx][ny] = nxt_h
                    q.appendleft((nx,ny,nxt_h,nxt_d,cnt+1))

    print(-1)
def point_validator(x,y):
    if x < 0 or y < 0 or x >= n or y >= n:
        return False
    return True
solv()