BOJ 14948 군대탈출하기(Python 3)

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

말이 되고픈 원숭이의 BFS유형과 이전에 글을 올린 Dragon Maze의 BFS유형을 합친 문제이다.

푸는 방법은 특수 장비를 쓸 수 있는 기회가 한 번 있고, 출발점에서 도착점까지 최소 레벨로 이동할 수 있는 레벨을 구하는 것이다.

생각은 간단하지만 막상 만들려고 하면 생각보다는 좀 길어서 혹시나 틀릴 경우 코드를 꼼꼼히 봐야 한다.

조심해야 하는 경우가 총 3가지가 있다.

1) 한 좌표 안에 특수 장비를 사용한 경우, 사용하지 않은 경우를 나눠서 값을 저장하기

2-1) 특수 장비를 쓰지 않았을 경우, 다음 방향으로 이동할 때 특수 장비를 사용하지 않을 때와 사용할 때로 나눠서 이동시키기

2-2) 특수 장비를 사용한 경우, 무조건 인접한 상하좌우 방향으로만 이동하기

3) 현재 좌표에서 필요한 레벨과 이전까지 이동했을 때의 필요한 최소 레벨 중 큰 값을 찾아 저장하기

세가지만 조심하면 충분히 맞을 수 있는 문제이다.

코드 확인

from collections import deque
Max=10**9
n,m=map(int,input().split())
D=[list(map(int,input().split())) for _ in range(n)]
S=[[[Max]*2 for _ in range(m)] for __ in range(n)]
q=deque()
q.append((0,0,0))
S[0][0][0]=D[0][0]
dx,dy=[1,-1,0,0],[0,0,-1,1]
while q:
    x,y,z=q.popleft()
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m and S[nx][ny][z]>max(S[x][y][z],D[nx][ny]):
            q.append((nx,ny,z))
            S[nx][ny][z]=max(S[x][y][z],D[nx][ny])
        nx+=dx[i];ny+=dy[i]
        if z==0 and 0<=nx<n and 0<=ny<m and S[nx][ny][z+1]>max(S[x][y][z],D[nx][ny]):
            q.append((nx,ny,z+1))
            S[nx][ny][z+1]=max(S[x][y][z],D[nx][ny])
if S[n-1][m-1][0]==Max:
    print(S[n-1][m-1][1])
elif S[n-1][m-1][1]==Max:
    print(S[n-1][m-1][0])
else:
    print(min(S[n-1][m-1]))