BOJ 12273 Dragon Maze(Python 3)

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

간단한 BFS문제이다.

그냥 음수값만 피하면서 이동시키며 BFS를 돌리고, 도착점에 도착하면 파워의 최대값을 계속 갱신할 수 있도록 만들면 된다.

비슷한 문제로는 '녹색 옷을 입은 얘가 젤다지?','군대탈출하기' 정도가 있다.

17~18줄 코드는 if문을 한 개로만 만들면 너무 길어서 가독성을 해칠 수가 있으므로, 두 개의 if로 나누어서 만들었다.

이 문제를 풀 수 있으면 Small도 풀 수 있으니 총 2문제나 풀 수 있으므로 매우 착한 문제이다.

코드확인

from collections import deque
dx,dy=[0,0,1,-1],[1,-1,0,0]
Max=10000
for ___ in range(int(input())):
    n,m=map(int,input().split())
    a,b,ax,ay=map(int,input().split())
    D=[list(map(int,input().split())) for _ in range(n)]
    S=[[[Max,-1] for __ in range(m)] for _ in range(n)]
    q=deque()
    q.append((a,b))
    S[a][b][0]=D[a][b]
    S[a][b][1]=D[a][b]
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<n and 0<=ny<m and D[nx][ny]!=-1:
                if S[nx][ny][0]>=S[x][y][0]+1 and S[nx][ny][1]<S[x][y][1]+D[nx][ny]:
                    q.append((nx,ny))
                    S[nx][ny][0]=S[x][y][0]+1
                    S[nx][ny][1]=S[x][y][1]+D[nx][ny]
    print('Case #{}:'.format(___+1),end=' ')
    print([S[ax][ay][1],'Mission Impossible.'][S[ax][ay][1]==-1])