[백준][누적합][구현] 27942 danceplant c++ 구현

목차

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

문제

 

문제 구현 방향

누적합을 통해 하지 않으면 시간초과가 나는 문제이다. 탐색은 bfs와 유사하게 했지만 가장 큰 곳을 먼저 탐색하게끔 좌표를 따로 저장해 주었다.

 

 

코드 구현

#include <iostream>
#include <vector>
#include<map>
#include<math.h>
#include <algorithm>


using namespace std;

typedef struct Plant{
    vector<pair<int, int>> v;
    int sum;
}Plant;
int N;
int board[3001][3001] = { 0 };
int searching[3001][3001] = { 0 };

vector<pair<int, int>> v;
//상하좌우
int dx[4] = {0,0,-1, 1};
int dy[4] = {-1, 1,0,0};

Plant direct[4];
int total = 0;
string str = "";

void init() {
    for (int i = 0; i < 4; i++) {
        direct[i].sum = 0;
    }
}

void convertPlus(int idx) {
    switch (idx)
    {
    case 0:
        str += "U";
        return;
    case 1:
        str += "D";
        return;
    case 2:
        str += "L";
        return;
    case 3:
        str += "R";
        return;
    default:
        break;
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    v.push_back({ N / 2 - 1, N / 2 - 1 });
    v.push_back({ N / 2 - 1, N / 2  });
    v.push_back({ N / 2 , N / 2  });
    v.push_back({ N / 2 , N / 2 - 1 });
    init();
    for (auto p : v) {
        searching[p.second][p.first] = 1;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    while (1) {
        for (auto p : v) {
            int x = p.first;
            int y = p.second;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1)continue;
                if (searching[ny][nx]) continue;
                direct[i].sum += board[ny][nx];
                direct[i].v.push_back({ nx,  ny });
                searching[ny][nx] = 1;
            }
        }

        int midx = 0;
        int M = -27;
        for (int i = 0; i < 4; i++) {
            if (M < direct[i].sum) {
                M = direct[i].sum;
                midx = i;
            }
        }
        if (M <= 0)break;
        total += M;
        convertPlus(midx);
        direct[midx].sum = 0;
        v.clear();
        for (auto p : direct[midx].v) {
            v.push_back({ p.first, p.second });
        }
        direct[midx].v.clear();

    }
    cout << total << "\n";
    cout << str;

    return 0;
}