[BOJ] 14948 군대 탈출하기

문제 요약

문제 링크: 백준 14948 - 군대 탈출하기

 

문제 설명
n x m 크기의 격자에서 각 칸에 숫자가 쓰여 있다.
(0,0)에서 (n-1, m-1)까지 이동하려고 한다.
이동은 상하좌우로 가능하며, 한 번만 벽을 뛰어넘을 수 있다.
이동할 때 지나는 칸의 숫자 중 최댓값이 최소가 되도록 하고 싶다.
이 최솟값을 구하는 문제이다.

 

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

 

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

---

접근 방법

• 이분 탐색(Binary Search)을 통해 가능한 최댓값을 정한다.
• BFS로 해당 값 이하로만 이동하면서, 벽을 한 번만 뛰어넘는 경우를 체크한다.
• 벽을 뛰어넘는 것은 두 칸을 한 번에 이동하는 것으로 처리한다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int n, m, mat[101][101], ans = 1e9;
int d[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};

void solve()
{
    int start = 0, end = 1e9, mid;
    while (start <= end)
    {
        mid = (start + end) / 2;
        bool vis[101][101][2], clear = 0;
        for (int i = 0; i < 101; i++)
        {
            for (int j = 0; j < 101; j++)
            {
                vis[i][j][0] = 0;
                vis[i][j][1] = 0;
            }
        }
        queue<tuple<int, int, int>> q;
        if (mid >= mat[0][0])
        {
            q.push({0, 0, 0});
            vis[0][0][0] = 1;
            vis[0][0][1] = 1;
            while (q.size())
            {
                int y = get<0>(q.front());
                int x = get<1>(q.front());
                int chk = get<2>(q.front());
                q.pop();
                if (y == n - 1 && x == m - 1)
                {
                    clear = 1;
                    break;
                }
                for (int i = 0; i < 4; i++)
                {
                    int yy = y + d[i][0];
                    int xx = x + d[i][1];
                    if (yy >= n || yy < 0 || xx >= m || xx < 0)
                        continue;
                    if (mat[yy][xx] <= mid)
                    {
                        if (vis[yy][xx][chk])
                            continue;
                        q.push({yy, xx, chk});
                        vis[yy][xx][chk] = 1;
                    }
                    else if (!chk)
                    {
                        int ny = yy + d[i][0];
                        int nx = xx + d[i][1];
                        if (ny >= n || ny < 0 || nx >= m || nx < 0)
                            continue;
                        if (vis[ny][nx][1])
                            continue;
                        if (mat[ny][nx] <= mid)
                        {
                            q.push({ny, nx, 1});
                            vis[ny][nx][1] = 1;
                        }
                    }
                }
            }
        }
        if (clear)
        {
            end = mid - 1;
            ans = min(ans, mid);
        }
        else
            start = mid + 1;
    }
    cout << ans;
}

void input()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cin >> mat[i][j];
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    solve();
}

---

푸는데 도움을 받은 반례

1. 막판에 9 한번 건너 뛰어야 함

10 10 
0 0 0 0 0 9 9 9 9 9
9 9 9 9 0 9 9 9 9 9
0 0 0 9 0 9 9 9 9 9
0 9 0 9 0 9 9 9 9 9
0 9 0 0 0 9 9 9 9 9
0 9 9 9 0 9 9 9 9 9
0 9 9 9 9 9 9 9 9 9
0 0 0 0 0 0 0 0 0 0
0 9 9 9 0 9 9 9 9 9
9 9 9 9 0 9 9 9 9 0

ans: 0

 

2. 시작점 자체를 건너뛸 수 없다

1 1
10 

ans: 10

 

3. 건너뛰는 로직 유의

1 2
4 3 

ans: 4

 

4. 2번 뛰어넘지 않는지 체크

5 6
5 5 5 5 7
100 7 7 7 7
5 7 7 7 7
7 5 7 7 7
7 7 5 7 7
7 7 7 5 5 

ans: 7

---

마무리

• 이 문제는 이분탐색 + BFS 조합이 핵심인 문제.
  벽을 한 번만 뛰어넘을 수 있다는 조건을 잘 처리하는 것이 중요함.
• 이분 탐색: 정답 범위(0 ~ 10⁹)를 log 스케일로 탐색 (약 30회 이내 연산)
  BFS: O(n × m × 4) = O(40,000)
  (n, m ≤ 100 → 최대 10,000 노드 × 4방향)
  예상 총 시간 복잡도: O(30 × 40,000) = O(1,200,000)