[백준 14948번] 파이썬 - 군대 탈출하기

백준 14948 - 군대 탈출하기

시간 제한 1초, 메모리 제한 256MB

# 조건

• 기윤이는 군대 탈출 게임을 좋아한다.
• 이 게임을 완료하기 위해서는 병영을 통과해 탈출해야 한다.
• 병영의 모습은 군기를 위해 항상 n x m 직사각형 모양이다.
• 블록(0,0)에서 출발하여 병영 밖으로 나가지 않고 상, 하, 좌, 우 4방향으로만 이동하여 블록(n-1,m-1)에 도착해야 병영을 탈출 한 것 이다.
  • 즉, 반드시 블록(0,0)과 블록(n-1,m-1)을 밟아야 한다.
• 각 블록은 레벨 제한이 있다.
• 만약 블록의 숫자가 3이라면 최소한 레벨 3이 되어야 그 블록을 지나갈 수 있다는 뜻이다.

• 위와 같은 병영이 주어졌을 때 병영을 탈출 하기 위해 필요한 레벨은 4이다.
  • (2-3-4-1-3-2 : 최댓값 4)
• 그러나 기윤이는 공군의 특수장비를 사용하여 단 한번 타일을 무시하고 건너뛰어 다음 타일로 갈 수 있다.
• 특수장비의 조건은 다음과 같다.
  1. 타일을 뛰어넘는 도중에 방향을 바꿀 수 없다.
  2. 병영 밖으로는 넘어갈 수 없다.
• 그러므로, 기윤이가 특수장비를 사용한 경우, 위의 예시에서 필요한 레벨의 최소 값은 3이다.
• 기윤이가 병영을 탈출하기 위해 달성해야 하는 최소한의 레벨을 알려주자!

입력

• 첫 줄에 각 병영의 세로 길이 n, 가로 길이 m 이 주어진다. (1 ≤ n, m ≤ 100)
• 다음 줄부터 차례대로 병영의 블록별 레벨 제한 k가 주어진다. (0 ≤ k ≤ 109).

출력

• 기윤이가 병영을 탈출하기 위해 달성해야 하는 최소한의 레벨을 출력한다.

# 접근 방법

• 가장 주의해야 할 점은 특수 장비의 사용 유무이다.
• 특수 장비를 이용하여 점프를 했는지 안했는지를 3차원 방문 배열을 이용하여 표시해준다.
• 기존 2차원 배열에서 각 좌표마다 [0, 0]으로 기록을 해주면서 3차원 배열을 사용해준다.
  • 0번은 사용안한 경우, 1번은 사용한 경우로 use 해준다.
• bfs를 돌리면서 방문하는데 방의 레벨이 현재 방문 기록의 레벨 보다 높다면 갱신해준다.
  • 점프 사용 유무가 -> 현재 기록할 3차원 인덱스가 0이라면, 점프를 사용하여 다다음 블록의 레벨로 저장해주고 점프 사용 유무를 1로 변경해주어 다시는 점프를 못하도록 저장해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs():  
    q = deque()  
    # 0, 0에서 출발, 점프 사용 유무  
    q.append((0, 0, 0))  
    # 초기 레벨 기록  
    visited[0][0][0] = arr[0][0]  
    while q:  
        si, sj, jump = q.popleft()  
        # 현재 경로에서 최고 레벨  
        val = visited[si][sj][jump]  
        for d in range(4):  
            ni, nj = si+di[d], sj+dj[d]  
            if 0<=ni<N and 0<=nj<M:  
                # 현재 밟고 있는 블록 레벨과 직전 블록까지의 최고레벨 비교  
                n_val = max(arr[ni][nj], val)  
                if visited[ni][nj][jump] > n_val:  
                    visited[ni][nj][jump] = n_val  
                    q.append((ni, nj, jump))  
                # 점프를 하지 않았다면 한칸 더 뛰어서 범위 내인지 체크  
                if jump == 0:  
                    ni+=di[d]  
                    nj+=dj[d]  
                    if 0<=ni<N and 0<=nj<M:  
                        n_val = max(arr[ni][nj], val)  
                        # 점프가 가능하므로 jump가 아닌 1로 변경해주어야 한다.  
                        if visited[ni][nj][1] > n_val:  
                            visited[ni][nj][1] = n_val  
                            q.append((ni, nj, 1))  

    print(min(visited[N-1][M-1]))  



N, M = map(int, input().split())  
arr = [[*map(int, input().split())] for _ in range(N)]  
visited = [[[float('inf')] * 2 for _ in range(M)] for _ in range(N)]  
di, dj = [1, -1, 0, 0], [0, 0, 1, -1]  
bfs()