[JAVA] 백준 14948. 군대탈출하기

📌 문제 링크 - https://www.acmicpc.net/problem/14948

 

 

---

 

 

 

 

문제

기윤이는 군대 탈출 게임을 좋아한다. 이 게임을 완료하기 위해서는 병영을 통과해 탈출해야 한다. 병영의 모습은 군기를 위해 항상 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 ≤ 10^9).

 

 

 

출력

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

 

 

 

 

 

 

---

 

 

풀이

이분 탐색과 bfs를 사용하여 풀 수 있는 문제다. 

 

이분 탐색을 통해 기윤이가 해당 레벨(mid)로 병영을 탈출할 수 있는지 bfs로 확인한다.

만약 해당 레벨로 탈출이 가능하다면 최소 레벨을 찾기 위해 end 값을 mid - 1로 조정해 주고, 

탈출이 불가능하다면 start 값을 mid + 1로 조정해 준다.

 

특수장비를 사용하여 타일을 건너뛰는 것은 한 번만 가능하므로 방문 체크를 해줄 때 3차원 배열을 사용하여 

[특수장비 사용 여부][행][열] 로 확인해가며 이동하면 된다. 

이때 주의할 점은 건너뛰었을 때의 타일도 레벨 제한보다 높을 수 있으므로 다시 한번 체크해 주어야 한다.

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// https://www.acmicpc.net/problem/14948
public class Main_14948 {
    private static final int[] dr = {-1, 1, 0, 0};
    private static final int[] dc = {0, 0, -1, 1};
    private static int N, M; // 병영의 세로 길이 N, 가로 길이 M
    private static int minLevel, maxLevel; // 최소 레벨, 최고 레벨
    private static int[][] map; // 병영의 블록별 레벨 제한


    public static void main(String[] args) throws IOException {
        init();

        int level = getLevel();
        System.out.print(level);
    }//main


    private static int getLevel() {
        Queue<int[]> q = new LinkedList<>();
        int level = 0; // 탈출하기 위해 달성해야 하는 최소한의 레벨
        int start = minLevel;
        int end = maxLevel;      
        int mid;

        while(start <= end) {
            mid = (start + end) / 2;

            if(isAvailable(mid, q)) { // 현재 레벨로 통과 가능
                end = mid - 1;
                level = mid;
            }
            else { // 불가능
                start = mid + 1;
            }

            q.clear();
        }

        return level;
    }//getLevel


    private static boolean isAvailable(int level, Queue<int[]> q) {
        if(level < map[0][0]) return false;
        
        boolean[][][] visited = new boolean[2][N][M]; // 방문 체크
        int r = 0, c = 0, used = 0;

        q.offer(new int[] {r, c, used});
        visited[used][r][c] = true;

        int[] cur;
        while(!q.isEmpty()) {
            cur = q.poll();
            r = cur[0]; // 행
            c = cur[1]; // 열
            used = cur[2]; // 장비 사용 여부 (0:미사용 1:사용 완료)

            if(r == N-1 && c == M-1) { // 탈출 완료
                return true;
            }

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

                if(rangeCheck(nr, nc) || visited[used][nr][nc]) continue;

                if(level >= map[nr][nc]) {
                    q.offer(new int[] {nr, nc, used});
                    visited[used][nr][nc] = true;
                }
                else {
                    if(used == 1) continue;

                    // 타일 건너뛰기
                    nr += dr[i];
                    nc += dc[i];

                    if(rangeCheck(nr, nc) || level < map[nr][nc]) continue;
                    if(visited[1][nr][nc]) continue;
                  
                    q.offer(new int[] {nr, nc, 1});
                    visited[1][nr][nc] = true;
                }
            }
        }

        return false;
    }//isAvailable


    private static boolean rangeCheck(int r, int c) {
        return r < 0 || r >= N || c < 0 || c >= M;
    }//rangeCheck


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 병영의 세로 길이 N, 가로 길이 M
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M]; // 병영의 블록별 레벨 제한
        minLevel = Integer.MAX_VALUE;

        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());

                minLevel = Math.min(minLevel, map[i][j]); // 최소 레벨
                maxLevel = Math.max(maxLevel, map[i][j]); // 최고 레벨
            }
        }

        br.close();
    }//init


}//class

/*
5 7
0 0 0 0 0 0 3
3 3 3 3 3 0 3
0 0 0 0 3 0 3
0 3 3 3 3 3 3
0 0 0 0 0 3 0
--
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
--
0
 */