[BOJ] 10251 : 운전 면허 시험

문제 링크

10251번: 운전 면허 시험 (acmicpc.net)

10251번: 운전 면허 시험

풀이

처음에는 그래프 탐색으로 풀어보려고 했다. 보통 그래프탐색은 상하좌우로 탐색하지만 이건 특별하게 오른쪽, 아래로만 탐색하는 그래프 탐색인 줄 알았다. 그래서 우선순위 큐를 만들어서 DP배열에 기름의 양과, 걸린시간을 모두 저장한다.탐색도중 기름의 양이 G를 넘어가면 그 경로로는 더이상 탐색을 하지 않는다.

이렇게 하려했더니 우선순위 큐에 들어가야 할 정보들이 너무 많았다 1. 좌표, 2. 기름의 총량, 3. 걸린 시간, 4. 방향 을 저장해야했다. 그래서 예제는 답이 나왔지만 제출 결과 메모리 초과가 났다. 잘못됐음을 깨닫고 알고리즘 분류를 봤더니 DP다. 이게 왜 DP지 의아했는데 DP배열을 DP[y좌표][x좌표][방향전환 횟수][방향] 이렇게 만들면 이해가 된다. 여기서 방향은 0 또는 1로 표시하고 위에서 왔는지 왼쪽에서 왔는지를 표시하는 인덱스이다. 나는 0은 위에서 1은 왼쪽에서 온것으로 간주했다. 

예를 들어, DP[y][x][k][0] 은 아래 또는 오른쪽으로 한 칸 갈 수 있다. 여기서 0은 위쪽 방향에서 왔다는 뜻이므로 아래쪽으로 이동할 경우 방향전환은 생기지 않는다. 그러나 오른쪽으로 갈 경우는 방향전환을 해야한다.

즉 DP[y+1][x][k][0]이 되거나 DP[y][x+1][k+1]][1]이 되거나 둘중 하나이다.

점화식을 세워보면 아래와 같다.

DP[i + 1][j][k][0] = min(DP[i + 1][j][k][0], DP[i][j][k][0] + Down[i][j]);
DP[i + 1][j][k + 1][0] = min(DP[i + 1][j][k + 1][0], DP[i][j][k][1] + Down[i][j]);

DP[i][j + 1][k][1] = min(DP[i][j + 1][k][1], DP[i][j][k][1] + Right[i][j]);
DP[i][j + 1][k + 1][1] = min(DP[i][j + 1][k + 1][1], DP[i][j][k][0] + Right[i][j]);

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int, int>, pair<pair<int, int>, bool>>, vector<pair<pair<int, int>, pair<pair<int, int>, bool>>>, greater<pair<pair<int, int>, pair<pair<int, int>, bool>>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 100 + 5;
int T;
int M, N, L, G;
int Right[MAX_N][MAX_N];
int Down[MAX_N][MAX_N];
int DP[MAX_N][MAX_N][2 * MAX_N][2];
 
bool is_ok(int y, int x) {
    if (y <= 0 || y > M || x <= 0 || x > N)
        return false;
    return true;
}
void Init() {
    memset(DP, 0x3f, sizeof(DP));
    DP[1][1][0][0] = DP[1][1][0][1] = 0;
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while (T--) {
        cin >> M >> N >> L >> G;
        Init();
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j < N; j++) {
                cin >> Right[i][j];
            }
        }
        for (int i = 1; i < M; i++) {
            for (int j = 1; j <= N; j++) {
                cin >> Down[i][j];
            }
        }
        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                for (int k = 0; k < 2 * max(M,N); k++) {
                    if (i + 1 <= M) {//아래로 이동
                        DP[i + 1][j][k][0] = min(DP[i + 1][j][k][0], DP[i][j][k][0] + Down[i][j]);
                        DP[i + 1][j][k + 1][0] = min(DP[i + 1][j][k + 1][0], DP[i][j][k][1] + Down[i][j]);
                    }
                    if (j + 1 <= N) {//오른쪽 이동
                        DP[i][j + 1][k][1] = min(DP[i][j + 1][k][1], DP[i][j][k][1] + Right[i][j]);
                        DP[i][j + 1][k + 1][1] = min(DP[i][j + 1][k + 1][1], DP[i][j][k][0] + Right[i][j]);
                    }
                }
            }
        }
        int ans = INF;
        for (int i = 0; i <= 2 * max(M,N); i++) {
            if (DP[M][N][i][0] <= G)
                ans = min(ans, (M + N - 2) * L + i);
            if (DP[M][N][i][1] <= G)
                ans = min(ans, (M + N - 2) * L + i);
        }
        if (ans == INF)
            cout << -1 << "\n";
        else cout << ans << "\n";
    }
    return 0;
}
 

이 문제를 풀면서 새롭게 알게된 정보가 있다. memset을 할 때 무한으로 초기화 하고싶을때는 어떻게 하나 궁금했는데 보통 0x3f 로 초기화를 시킨다고 한다. 물론 0x3f 를 두 배해도 INT_MAX값 보다는 작다고 한다.