백준 21923 곡예 비행 (C++)

https://www.acmicpc.net/problem/21923

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int udy[2] = {0, -1};
int udx[2] = {1, 0};

int ddy[2] = {0, -1};
int ddx[2] = {-1, 0};

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<int>> arr(n, vector<int>(m));
    vector<vector<int>> udp(n, vector<int>(m, -987654321));
    vector<vector<int>> ddp(n, vector<int>(m, -987654321));

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


    //상승 비행
    udp[n - 1][0] = arr[n - 1][0];


    queue<pair<int, int>> queue1;
    queue1.push(make_pair(n - 1, 0));

    while (!queue1.empty()) {
        pair<int, int> cur = queue1.front();
        queue1.pop();


        for (int k = 0; k < 2; k++) {
            pair<int, int> ncur = make_pair(cur.first + udy[k], cur.second + udx[k]);

            if (ncur.first >= 0 && ncur.first < n && ncur.second >= 0 && ncur.second < m &&
                udp[ncur.first][ncur.second] < udp[cur.first][cur.second] + arr[ncur.first][ncur.second]) {
                queue1.push(ncur);
                udp[ncur.first][ncur.second] = udp[cur.first][cur.second] + arr[ncur.first][ncur.second];
            }
        }

    }

    //하강 비행
    ddp[n-1][m - 1] = arr[n-1][m - 1];


    queue<pair<int, int>> queue2;
    queue2.push(make_pair(n-1, m - 1));

    while (!queue2.empty()) {
        pair<int, int> cur = queue2.front();
        queue2.pop();


        for (int k = 0; k < 2; k++) {
            pair<int, int> ncur = make_pair(cur.first + ddy[k], cur.second + ddx[k]);

            if (ncur.first >= 0 && ncur.first < n && ncur.second >= 0 && ncur.second < m &&
                ddp[ncur.first][ncur.second] < ddp[cur.first][cur.second] + arr[ncur.first][ncur.second]) {
                queue2.push(ncur);
                ddp[ncur.first][ncur.second] = ddp[cur.first][cur.second] + arr[ncur.first][ncur.second];
            }
        }

    }

    int ans = -987654321;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans = max(ans, udp[i][j] + ddp[i][j]);
        }
    }

    cout << ans;


    return 0;
}

1. 문제

문제

동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 점수는 "상승 비행을 할 때 지나간 칸에 부여된 점수의 총합"과 "하강 비행을 할 때 지나간 칸에 부여된 점수의 총합"을 더한 값이다. 출발한 칸과 도착한 칸도 지나간 칸으로 간주한다.

<그림 1> 시작과 끝 칸 및 가능한 이동 방향

모형 비행기는 맨 왼쪽 아래 칸에서 상승 비행으로 비행을 시작해야 하고, 중간에 상승 비행에서 하강 비행으로 변경한 후, 맨 오른쪽 아래 칸에서 하강 비행으로 비행을 종료해야 한다. 상승 비행에서 하강 비행으로 변경할 때에는 다른 칸으로 이동할 수 없다. 즉, 상승 비행이 끝난 칸에서 하강 비행을 시작해야 한다.

모형 비행기는 상승 비행 중에는 앞 또는 위로만 이동할 수 있고, 하강 비행 중에는 앞 또는 아래로만 이동할 수 있다.

<그림 2> 모형 비행기의 이동 경로

위의 예시에서, 각 칸에 적힌 수는 그 칸에 부여된 점수이고, 수가 적혀 있지 않은 칸의 점수는 0이라고 가정하자. 그리고 모형 비행기가 1, 2, ..., 15의 순서대로 비행을 했다고 가정하자.

<그림 3> 상승 비행의 이동 경로

<그림 4> 하강 비행의 이동 경로

이 경우, 상승 비행은 1이 적힌 칸에서 시작하고 8이 적힌 칸에서 끝난다. 하강 비행은 8이 적힌 칸에서 시작하고 15가 적힌 칸에서 끝난다. 이와 같이 비행을 하였을 때 얻는 점수는 (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8) + (8 + 9 + 10 + 11 + 12 + 13 + 14 + 15) = 128 이다.

동헌이는 이 대회에서 얻을 수 있는 최대 비행 점수가 궁금하다. 동헌이를 위해 얻을 수 있는 최대 비행 점수를 구해주자.

입력

첫째 줄에 심사위원들이 나눠놓은 구역(격자)의 세로 길이 𝑁, 가로 길이 𝑀이 공백과 함께 주어진다.

두 번째 줄부터 𝑁+1번째 줄까지, 각 칸에 해당하는 점수가 한 줄에 한 행씩 공백과 함께 주어진다.

출력

동헌이가 얻을 수 있는 최대 점수를 출력하라.

제한

•  1≤𝑁,𝑀≤1,000
•  -10,000 ≤ 점수 ≤10,000

2. 풀이

상승비행 후 하강 비행을 하는 문제이므로 상승 비행과 하강 비행으로 나누어 풀 수 있다.

2-1 상승 비행

int udy[2] = {0, -1};
int udx[2] = {1, 0};

//상승 비행
    udp[n - 1][0] = arr[n - 1][0];


    queue<pair<int, int>> queue1;
    queue1.push(make_pair(n - 1, 0));

    while (!queue1.empty()) {
        pair<int, int> cur = queue1.front();
        queue1.pop();


        for (int k = 0; k < 2; k++) {
            pair<int, int> ncur = make_pair(cur.first + udy[k], cur.second + udx[k]);

            if (ncur.first >= 0 && ncur.first < n && ncur.second >= 0 && ncur.second < m &&
                udp[ncur.first][ncur.second] < udp[cur.first][cur.second] + arr[ncur.first][ncur.second]) {
                queue1.push(ncur);
                udp[ncur.first][ncur.second] = udp[cur.first][cur.second] + arr[ncur.first][ncur.second];
            }
        }

    }

상승 비행은 (n-1, 0)에서 시작한다. 해당 위치에서 우측 또는 상향의 방향으로 비행하면서 BFS를 돌리면서 상승 비행 시의 최대 비행 점수를 구한다.

2-2 하강 비행

int ddy[2] = {0, -1};
int ddx[2] = {-1, 0};

//하강 비행
    ddp[n-1][m - 1] = arr[n-1][m - 1];


    queue<pair<int, int>> queue2;
    queue2.push(make_pair(n-1, m - 1));

    while (!queue2.empty()) {
        pair<int, int> cur = queue2.front();
        queue2.pop();


        for (int k = 0; k < 2; k++) {
            pair<int, int> ncur = make_pair(cur.first + ddy[k], cur.second + ddx[k]);

            if (ncur.first >= 0 && ncur.first < n && ncur.second >= 0 && ncur.second < m &&
                ddp[ncur.first][ncur.second] < ddp[cur.first][cur.second] + arr[ncur.first][ncur.second]) {
                queue2.push(ncur);
                ddp[ncur.first][ncur.second] = ddp[cur.first][cur.second] + arr[ncur.first][ncur.second];
            }
        }

    }

 하강 비행은 (n-1, m-1)에 도착하고, 시작 위치는 특정할 수 없다. 반대로 말하자면 (n-1, m-1)에서 시작하는 좌상향 비행을 한다고 생각할 수 있다. 상승 비행 시와 같은 원리로 BFS를 이용하여 탐색한다.

    int ans = -987654321;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            ans = max(ans, udp[i][j] + ddp[i][j]);
        }
    }

    cout << ans;

udp는 (n-1, 0)에서 해당 위치까지 도착했을 때의 비행 점수이고, ddp는 해당 위치에서 (n-1, m-1)에 도착할 때 까지의 비행 점수이다. 이를 더한 값중 최댓값을 출력하여 정답을 구할 수 있다.