SW Expert Academy 5644. 무선 충전

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE

걸린 시간

-

풀이

C++

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;

int dy[5] = {0, -1, 0, 1, 0};
int dx[5] = {0, 0, 1, 0, -1};
int visited[10][10];

void bc(int y, int x, int c, int ap, vector<int> Map[10][10]){
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    Map[y][x].push_back(ap);
    visited[y][x] = 1;
    int depth = 0;
    while(!q.empty()){
        depth++;
        int size = q.size();
        if(depth > c) break;
        for(int i = 0; i < size; i++){
            int cy = q.front().first;
            int cx = q.front().second;
            q.pop();
            for(int j = 1; j <= 4; j++){
                int ny = cy+dy[j];
                int nx = cx+dx[j];
                if(0 <= ny && ny < 10 && 0 <= nx && nx < 10){
                    if(!visited[ny][nx]){
                        visited[ny][nx] = 1;
                        q.push(make_pair(ny, nx));
                        Map[ny][nx].push_back(ap);
                    }
                }
            }
        }
    }
}

int main()
{
    int test_case;
    int T;
    cin >> T;
    for(test_case = 1; test_case <= T; ++test_case)
    {
        int m, a;
        cin >> m >> a;
        vector<int> A, B, P;
        vector<int> Map[10][10];
        A.resize(m); B.resize(m); P.resize(a);
        for(int& i : A) cin >> i;
        for(int& i : B) cin >> i;
        int y, x, c, p;
        for(int i = 0; i < a; i++){
            cin >> x >> y >> c >> p;
            bc(y-1, x-1, c, i, Map);
            P[i] = p;
        }
        int ans = 0;
        int ay, ax, by, bx;
        ay = ax = 0;
        by = bx = 9;
        auto AA = Map[ay][ax];
        auto BB = Map[by][bx];
        int tmp = 0;
        for(int i = 0; i < AA.size(); i++) tmp = max(tmp, P[AA[i]]);
        for(int i = 0; i < BB.size(); i++) tmp = max(tmp, P[BB[i]]);
        for(int i = 0; i < AA.size(); i++){
            for(int j = 0; j < BB.size(); j++){
                if(AA[i] == BB[j])
                    tmp = max(tmp, P[AA[i]]/2 + P[BB[j]]/2);
                else
                    tmp = max(tmp, P[AA[i]] + P[BB[j]]);
            }
        }
        ans += tmp;
        for(int i = 0; i < m; i++){
            ay += dy[A[i]];
            ax += dx[A[i]];
            by += dy[B[i]];
            bx += dx[B[i]];
            auto AA = Map[ay][ax];
            auto BB = Map[by][bx];
            int tmp = 0;
            for(int i = 0; i < AA.size(); i++) tmp = max(tmp, P[AA[i]]);
            for(int i = 0; i < BB.size(); i++) tmp = max(tmp, P[BB[i]]);
            for(int i = 0; i < AA.size(); i++){
                for(int j = 0; j < BB.size(); j++){
                    if(AA[i] == BB[j])
                        tmp = max(tmp, P[AA[i]]/2 + P[BB[j]]/2);
                    else
                        tmp = max(tmp, P[AA[i]] + P[BB[j]]);
                }
            }
            ans += tmp;
        }
        cout << "#" << test_case << " " << ans << "\n";
    }
    return 0;
}

현재의 선택이 다음 결과에 영향을 끼칠지 고려하지 않아도 되고, 각 부분 문제(시간)의 최적해로 전체 문제의 최적해를 구할 수 있으므로 greedy 알고리즘을 구현하여 풀이하였다.