백준 25919 Lost Edge 파이썬

https://www.acmicpc.net/problem/25919

25919번: Lost Edge

대회 문제중에 풀만한 문제를 찾아보던중 발견한 문제였다.

일반적인 BFS와 다른 점은 heapq과 같이 사용한다는 것이였다. 왔던길을 다시 갈 수 있으므로 갈 수 있는 길을 모두 heapq에 담아 자신의 레벨보다 작은 몬스터들을 먼저 죽여 레벨업을 하면서 갈 수 있는 길을 넓여가면 된다.

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

def bfs():
    global L,E
    vist=[[False]*m for _ in range(n)]
    h=[]
    while q:
        x,y = q.popleft()
        for o in range(4):#4가지 방향 탐색
            nx=dx[o]+x
            ny=dy[o]+y
            if 0<=nx<n and 0<=ny<m and s[nx][ny]>=0 and not vist[nx][ny]:#방문 했던 곳 and 벽 and 레이드 장소 제외
                vist[nx][ny]=True#방문 표시
                heapq.heappush(h,(s[nx][ny],nx,ny))#heapq에 추가해줌 몬스터 레벨과 좌표
        while h and h[0][0]<L:#처치할 수 있는 몬스터가 있다.
            w,i,j=heapq.heappop(h)
            E += w#경험치 추가
            if E>=L:#레벨업 가능
                while E>=L:#레벨업 해줌
                    E-=L
                    L+=1
            q.append((i,j))#몬스터를 처리했으니 갈 수 있는 길이 넓어짐
            s[i][j]= 0#더이상 경험치를 안 주니 0으로 설정
def find():#일반적인 BFS방법이다. *벽과 자신의 레벨보다 높은 몬스터가 있는 지역만 못 지나가는*
    while f:
        x,y = f.popleft()
        if x==en[0] and y==en[1]:#레이드 지역에 도착하면 O출력해주고 종료
            print("O")
            return
        h = []
        for o in range(4):
            nx=dx[o]+x
            ny=dy[o]+y
            if 0<=nx<n and 0<=ny<m and s[nx][ny]!=-1 and not vist[nx][ny] and s[nx][ny]<L:#자신의 레벨보다 높아서 못 지나감
                vist[nx][ny]=True
                f.append((nx,ny))
    print("X")#탐색이 끝났는데 도달하지 못 했기에 X출력
n,m = map(int,input().split())
L,E,K = map(int,input().split())
s = [list(map(int,input().split())) for _ in range(n)]
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for i in range(n):
    for j in range(m):
        if s[i][j]==-3:
            s[i][j]=0
            q=deque()
            f=deque()
            f.append((i,j))
            q.append((i,j))
        elif s[i][j]==-2:
            en = ((i,j))
w = bfs()
if L>=K:목표 레벨을 달성했으므로 BFS를 돌려 레이드 장소로 가야함.
    vist=[[False]*m for _ in range(n)]
    find()
else:#달성하지 못 했으므로 X출력
    print("X")