[파이썬] 백준 22944 : 죽음의 비 (골드3)

[파이썬] 백준 22944 : 죽음의 비 (골드3)

---

문제

---

풀이

0. 방향성 생각

• S에서 시작해서 우산 내구도가 있는 상태면 우산 내구도부터 깎고, 아닌 경우 HP깎는 방식으로 진행.

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,hp,shield = map(int,input().split())
arr = [list(input()) for _ in range(n)]

for i in range(n):
    for j in range(n):
        if arr[i][j] == 'S':
            sx,sy = j,i
        if arr[i][j] == 'E':
            ex,ey = j,i

visit = [[0]*n for _ in range(n)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]

• 시작위치는 sx,sy로 끝 위치는 ex,ey로
• visit에는 현재 HP+쉴드량을 저장해준다.
• visit에 시간을 저장하는 경우에는 새로 갱신이 되더라도 HP가 부족해서 도착점에 도달하지 못하는 경우가 생긴다.

2. BFS

q = deque([(hp,0,sx,sy,0)])
visit[sy][sx] = hp
answer = []
while q:
    HP,barrier,x,y,t = q.popleft()

    if (x,y) == (ex,ey):
        answer.append(t)

    for dx,dy in dire:
        nx,ny = x+dx,y+dy
        
        if 0<=nx<n and 0<=ny<n:
            if arr[ny][nx] == '.' and (HP-1)+barrier > visit[ny][nx]:
                visit[ny][nx] = (HP-1)+barrier
                if barrier:
                    q.append((HP,barrier-1,nx,ny,t+1))
                else:
                    q.append((HP-1,0,nx,ny,t+1))
                    
            elif arr[ny][nx] == 'U' and HP+(shield-1) > visit[ny][nx]:
                visit[ny][nx] = HP+(shield-1)
                q.append((HP,shield-1,nx,ny,t+1))
                
            elif arr[ny][nx] == 'E' and HP+barrier > visit[ny][nx]:
                visit[ny][nx] = HP+barrier
                q.append((HP,barrier,nx,ny,t+1))
                
print(min(answer)) if answer else print(-1)

• 큐에다가 넣고 BFS 진행
• .을 방문하는 경우에는 베리어 유무를 고려하기
• U를 방문하는 경우에는 우산을 쓰면서 바로 우산 내구도 깎아주기 (test case 3)
• E에 방문하면 정답 리스트에 추가
• answer가 비어있으면 -1 아니면 최소값 출력하기

 

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

n,hp,shield = map(int,input().split())
arr = [list(input()) for _ in range(n)]

for i in range(n):
    for j in range(n):
        if arr[i][j] == 'S':
            sx,sy = j,i
        if arr[i][j] == 'E':
            ex,ey = j,i

visit = [[0]*n for _ in range(n)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]


q = deque([(hp,0,sx,sy,0)])
visit[sy][sx] = hp
answer = []
while q:
    HP,barrier,x,y,t = q.popleft()

    if (x,y) == (ex,ey):
        answer.append(t)
        
    for dx,dy in dire:
        nx,ny = x+dx,y+dy
        
        if 0<=nx<n and 0<=ny<n:
            if arr[ny][nx] == '.' and (HP-1)+barrier > visit[ny][nx]:
                visit[ny][nx] = (HP-1)+barrier
                if barrier:
                    q.append((HP,barrier-1,nx,ny,t+1))
                else:
                    q.append((HP-1,0,nx,ny,t+1))
                    
            elif arr[ny][nx] == 'U' and HP+(shield-1) > visit[ny][nx]:
                visit[ny][nx] = HP+(shield-1)
                q.append((HP,shield-1,nx,ny,t+1))
                
            elif arr[ny][nx] == 'E' and HP+barrier > visit[ny][nx]:
                visit[ny][nx] = HP+barrier
                q.append((HP,barrier,nx,ny,t+1))
                
print(min(answer)) if answer else print(-1)

 

코멘트

다익으로 먼저 풀고 시간 t를 visit에 배열에 저장했는데 68%에서 자꾸 틀려서 HP를 visit에 저장

다익으로 시간초과나서 BFS로 바꿨음.

시작, 끝 위치 상관없다고 생각해서 둘 다 loc에 할당하고 앞에있는거를 S에 뒀는데, 우산 위치에 따라서 안되는걸 생각 못해서 삽질했다......

 

시간이 덜 걸리는 코드들을 살펴보니, S,U,E만 node로 생각해서 edges 정보는 맨하탄 거리로 변환해서 생각한다.

현재 체력에 대해서 갈 수 있는 node, 없는 node가 나뉘어있고 필요없는 이동도 줄일 수 있어서 시간을 크게 줄일 수 있다.