백준 14948 - 군대 탈출하기 (C++)

문제

• 문제 링크

  
   BOJ 14948 - 군대 탈출하기 
  

• 문제 요약

$N*M$의 맵이 주어지고 $(1, 1)$에서 $(N, M)$으로 이동하려 한다.
최소 각 칸에 적힌 레벨만큼은 되어야 해당 칸을 지날 수 있고 딱 한 번 한 칸을 건너뛸 수 있을 때, 갖춰야 하는 최소 레벨을 구해보자.

• 제한

TL : $1$ sec, ML : $256$ MB




$1 ≤ n, m ≤ 100$

$0 ≤ k ≤ 10^9$

알고리즘 분류

• 그래프 이론(graphs)
• 그래프 탐색(graph_traversal)
• 너비 우선 탐색(bfs)
• 이분 탐색(binary search)
• 매개 변수 탐색(parametric search)

풀이

문제 내용과 $k$의 범위만 봐도 파라매트릭 냄새가 솔솔 난다. 다음과 같이 결정 문제를 정의해보자.

$f(x)$ : 최소 레벨을 $x$라 했을 때 $(N, M)$에 도달할 수 있는가?

결정 문제를 풀 때 좌표 이외에 특수 장비를 사용 했는지 ? 에 대한 상태가 추가된다.
이에 따라 각 결정 문제를 $O(2*N*M)$에 풀 수 있으므로 총 $O(logK * N*M)$의 복잡도로 문제를 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int dy[]{ -1, 1, 0, 0 }, dx[]{ 0, 0, -1, 1 };
int n, m, M[101][101];
 
int f(int mid)
{
    if (M[1][1] > mid) return 0;
    queue <tuple<int, int, bool>> Q;
    int V[101][101][2]{};
    Q.push({ 1, 1, 0 }); V[1][1][0] = 1;
    while (Q.size())
    {
        auto [a, b, c](Q.front()); Q.pop();
        if (a == n && b == m) return 1;
        for (int i{}; i < 4; i++)
        {
            int y(a + dy[i]), x(b + dx[i]);
            if (y && x && y <= n && x <= m && M[y][x] <= mid && !V[y][x][c])
                V[y][x][c] = V[a][b][c] + 1, Q.push({ y, x, c });
        }
        for (int i{}; !c && i < 4; i++)
        {
            int y(a + dy[i] * 2), x(b + dx[i] * 2);
            if (y > 0 && x > 0 && y <= n && x <= m && M[y][x] <= mid && !V[y][x][1])
                V[y][x][1] = V[a][b][c] + 1, Q.push({ y, x, 1 });
        }
    }
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i(1); i <= n; i++)
        for (int j(1); j <= m; cin >> M[i][j++]);
    int p{}, q(1e9), r{};
    while (p <= q)
    {
        int m((p + q) >> 1);
        f(m) ? q = m - 1, r = m : p = m + 1;
    }
    cout << r;
}

comment

끝