백준 14948

군대 탈출

기윤이는 군대 탈출 게임을 좋아한다. 이 게임을 완료하기 위해서는 병영을 통과해 탈출해야 한다. 병영의 모습은 군기를 위해 항상 n x m 직사각형 모양이다.

블록(0,0)에서 출발하여 병영 밖으로 나가지 않고 상, 하, 좌, 우 4방향으로만 이동하여 블록(n-1,m-1)에 도착해야 병영을 탈출 한 것 이다. 즉, 반드시 블록(0,0)과 블록(n-1,m-1)을 밟아야 한다.

각 블록은 레벨 제한이 있다. 만약 블록의 숫자가 3이라면 최소한 레벨 3이 되어야 그 블록을 지나갈 수 있다는 뜻이다.

4x3 병영 타일 번호

타일 레벨 제한

위와 같은 병영이 주어졌을 때 병영을 탈출 하기 위해 필요한 레벨은 4이다.

(2-3-4-1-3-2 : 최댓값 4)

그러나 기윤이는 공군의 특수장비를 사용하여 단 한번 타일을 무시하고 건너뛰어 다음 타일로 갈 수 있다.

특수장비의 조건은 다음과 같다.

1. 타일을 뛰어넘는 도중에 방향을 바꿀 수 없다.
2. 병영 밖으로는 넘어갈 수 없다.

그러므로, 기윤이가 특수장비를 사용한 경우, 위의 예시에서 필요한 레벨의 최소 값은 3이다.

(2-3-(12)-1-3-2 : 최댓값 3)

기윤이가 병영을 탈출하기 위해 달성해야 하는 최소한의 레벨을 알려주자!

 

문제 해석

탈출할 수 있는 최대 레벨 계산하는 것

 

바로 메모리 펑 ㅋㅋ

 

문제가 뭘까

백트레킹 해야하는 걸까?

지금 떠올릴만한 백트레킹은 한 좌표를 찍는데, 그 좌표보다 맥스 값이 작은 놈만 찍도록 하는 것이다. 

그리고 또 잘못된 점이 있다

상으로는 못가도 좌우하로 움직여야한다

그리고 이동 시 3방향으로 그냥 점프가 가능하다. 

문제해석을 잘못했다.

ㅎ히ㅣㅎ히

7 7

0 0 0 0 0 0 3
3 3 3 3 3 0 3
3 3 3 3 3 0 3
0 0 0 0 3 0 3
0 3 3 3 3 3 3
0 3 3 3 3 3 3
0 0 0 0 0 0 0

다시 말하자면

이런 모양을 통과할 수 있어야 한다

 

4방향 설정 이상하게 해놔서 5번인가 내리틀렸다 

부끄럽다 ㅎㅎ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;

class info{
    int r,c,max,status;
    public info(int r, int c, int max, int status){
        this.r=r;
        this.c=c;
        this.max=max;
        this.status=status;
    }
}

public class Main {
    static int [] dr = {-1,1,0,0};
    static int [] dc = {0,0,1,-1};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());;
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int [][] map = new int[N][M];
        int [][][] bTr = new int[2][N][M];

        for(int i =0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j =0; j<M; j++){
                map[i][j]=Integer.parseInt(st.nextToken());
                bTr[0][i][j]=Integer.MAX_VALUE;
                bTr[1][i][j]=Integer.MAX_VALUE;
            }
        }
        int answer = Integer.MAX_VALUE;

        ArrayDeque<info> q = new ArrayDeque<>();
        q.add(new info(0,0,map[0][0],1));

        while (!q.isEmpty()){
            info cur = q.poll();
            int r = cur.r;
            int c = cur.c;
            int max = cur.max;
            int status = cur.status;
//            System.out.println("현 위치"+ r +" " + c);
//            System.out.println("현 최고 값"+ max);
//            System.out.println("필살기 유무"+ status);
//            System.out.println();
//            System.out.println();

            if(r==N-1 && c==M-1){
                answer = Math.min(max,answer);
                continue;
            }

            for(int i =0; i<4; i++){
                int nr = r+dr[i];
                int nc = c+dc[i];

                if(0<=nr && nr<N && 0<=nc && nc<M && bTr[status][nr][nc]>max){
                    q.add(new info(nr,nc,Math.max(max,map[nr][nc]),status));
                    bTr[status][nr][nc]=max;
                }
            }

            if(status==1){//필살기 가능할 때
                for(int i =0; i<4; i++){
                    int nr = r + dr[i] +dr[i];
                    int nc = c + dc[i] +dc[i];
                    if(0<=nr && nr<N && 0<=nc && nc<M && bTr[0][nr][nc]>max){
                        q.add(new info(nr,nc,Math.max(max,map[nr][nc]),0));
                        bTr[0][nr][nc]=max;
                    }
                }
            }
        }
        System.out.println(answer);
    }

}