[c++][백준 21923][BFS] 곡예 비행 - 컴도리돌이

---

 

21923번: 곡예 비행

---

풀이 과정

 

상향과 하향을 나누어서 BFS 탐색을 하였다.

(상향) 방향은 위, 오른쪽으로 오른쪽과 위로만 탐색하며, 정해진 2차원 배열 안에서 시작점부터 오른쪽 모서리까지 이동하면서 최대 이동 값을 저장한다.

(하향) 방향은 위, 왼쪽으로 왼쪽과 위로만 탐색하며, 정해진 2차원 배열 안에서 끝점에서 왼쪽 모서리까지 이동하면서 최대 이동 값을 저장한다.

끝점과 시작점의 BFS 탐색이 끝났으면 위치에 따른 둘의 합이 제일 큰 값을 출력한다.

---

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

using namespace std;

int n,m;
vector<vector<int>> matrix;

void input(){
    cin >> n >> m;

    matrix.resize(n,vector<int>(m));

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

vector<vector<int>> bfs(int x,int y,int flag){
    vector<vector<int>> temp(n,vector<int>(m,INT32_MIN));
    temp[x][y] = matrix[x][y];
    int dx[] = {-1,0};
    int dy[] = {0,1};

    queue<pair<int,int>> q;
    q.push({x,y});

    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<2; i++){
            int nx = x + dx[i];
            int ny = y + dy[i] * flag;
            if( nx < 0 or ny < 0 or nx >= n or ny >= m) continue;
            if(temp[nx][ny] < temp[x][y] + matrix[nx][ny]){
                temp[nx][ny] = temp[x][y] + matrix[nx][ny];
                q.push({nx,ny});
            }
        }
    }
    return temp;
}

void solution(){
    vector<vector<int>> upper = bfs(n-1,0,1);
    vector<vector<int>> lower = bfs(n-1,m-1,-1);

    int ans = INT32_MIN;
    for(int i=0; i<n; i++)
        for(int j=0; j<m ;j++)
            if(upper[i][j] + lower[i][j] > ans){
                ans = upper[i][j] + lower[i][j];
            }
    cout << ans;
}

int main(){
    input();
    solution();
    return 0;
}