5644. [모의 SW 역량테스트] 무선 충전

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo

SW Expert Academy

문제접근법

 

1. BC의 거리 범위에 맞게 BFS 탐색을 통해서, 2차원 자료 구조에 표시해줘야 한다. 단, 2차원 자료 구조로 배열을 선택할 시에, 한 칸에 하나의 BC밖에 못들어가므로, 벡터 자료구조를 사용한다.

 

2. A와 B의 위치에 따라서 충전량을 더해줘야 한다. 충전량을 더할 때 케이스 분류가 필요하다. A와 B가 같은 BC에 있을 때, A와 B가 1개의 BC만 가진다면 나눠 쓰는게 맞다. 하지만, A나 B가 2개 이상의 BC를 가진다면, 한 사람만 다른 BC중에서 충전량이 가장 높은 것을 사용하면 된다. 위와 같은 방식이 적용될 수 있게 케이스 분류가 필요하다.

 

이 문제는 케이스 분류를 잘해줘야 하는 문제이다.

 

유의사항

 

문제에서 제공하고 있는 x, y는, 평소에 알고리즘 행과 열에 익숙해진 사람이라면 y, x로 바꿔서 푸는 것을 추천한다.

 

해설코드

#include <queue>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
 
typedef struct item {
    int r, c, time, p;
    item(int _r, int _c, int _t, int _p) :r(_r), c(_c), time(_t), p(_p) {};
}item;
 
typedef struct item2 {
    int AC, P;
    item2(int _ac, int _p) :AC(_ac), P(_p) {};
}item2;
 
struct myfunc {
    bool operator()(item2 i1, item2 i2) {
        return i1.P > i2.P;
    }
} myfunc;
 
int T;
int M, A;
int op[5][2] = { {0,0},{-1,0},{0,1},{1,0},{0,-1} };
int M_A[1001] = {};
int M_B[1001] = {};
int r1, r2, r3, r4;
 
int main(void) {
    //freopen("input.txt", "r", stdin);
    cin >> T;
 
    for (int t = 1; t <= T; t++) {
        vector<item> v;
        vector<item2> map[11][11];
 
        int A_r = 1;
        int A_c = 1;
        int B_r = 10;
        int B_c = 10;
 
        int result_A = 0;
        int result_B = 0;
        int answer = 0;
 
        memset(map, 0, sizeof(map));
        cin >> M >> A;
 
        for (int m = 0; m < M; m++)
            cin >> M_A[m];
 
        for (int m = 0; m < M; m++)
            cin >> M_B[m];
 
        for (int i = 0; i < A; i++) {
            cin >> r1 >> r2 >> r3 >> r4;
            v.push_back(item(r2, r1, r3, r4));
            map[r2][r1].push_back(item2(i + 1, r4));
        }
 
        // BFS
        for (int i = 0; i < v.size(); i++) {
            int check[11][11] = { 0 };
            memset(check, 0, sizeof(check));
 
            int r = v.at(i).r;
            int c = v.at(i).c;
            int time = v.at(i).time;
            int p = v.at(i).p;
 
            queue<item> q;
            q.push(item(r, c, 0, p));
            check[r][c] = 1;
 
            while (!q.empty()) {
                int q_r = q.front().r;
                int q_c = q.front().c;
                int q_t = q.front().time;
                q.pop();
 
                for (int o = 1; o <= 4; o++) {
                    int n_r = q_r + op[o][0];
                    int n_c = q_c + op[o][1];
                    if (n_r < 1 || n_c < 1 || n_r > 10 || n_c > 10 || check[n_r][n_c] == 1)
                        continue;
 
                    if (q_t == time)
                        break;
 
                    q.push(item(n_r, n_c, q_t + 1, p));
                    map[n_r][n_c].push_back(item2(i + 1, p));
                    check[n_r][n_c] = 1;
                }
            }
        }
 
        // MOVE
        for (int m = 0; m <= M; m++) {
            sort(map[A_r][A_c].begin(), map[A_r][A_c].end(), myfunc);
            sort(map[B_r][B_c].begin(), map[B_r][B_c].end(), myfunc);
 
            if (map[A_r][A_c].size() >= 1 && map[B_r][B_c].size() >= 1) {
                int A_ac = map[A_r][A_c].front().AC;
                int B_ac = map[B_r][B_c].front().AC;
 
                if (A_ac != B_ac) {
                    answer += map[A_r][A_c].front().P;
                    answer += map[B_r][B_c].front().P;
                }
                else if (A_ac == B_ac) {
                    int A_tmp1 = map[A_r][A_c].front().AC;
                    int A_tmp2 = map[A_r][A_c].front().P;
 
                    int B_tmp1 = map[B_r][B_c].front().AC;
                    int B_tmp2 = map[B_r][B_c].front().P;
 
                    if (map[A_r][A_c].size() == 1 && map[B_r][B_c].size() == 1) {
                        answer += map[A_r][A_c].front().P;
                    }
                    else if(map[A_r][A_c].size() > 1 && map[B_r][B_c].size() > 1){
                        if (map[A_r][A_c].at(1).P > map[B_r][B_c].at(1).P) {
                            answer += A_tmp2 + map[A_r][A_c].at(1).P;
                        }
                        else {
                            answer += B_tmp2 + map[B_r][B_c].at(1).P;
                        }
                    }
                    else if (map[A_r][A_c].size() == 1 && map[B_r][B_c].size() > 1) {
                        answer += A_tmp2;
                        answer += map[B_r][B_c].at(1).P;
                    }
                    else if (map[A_r][A_c].size() > 1 && map[B_r][B_c].size() == 1) {
                        answer += B_tmp2;
                        answer += map[A_r][A_c].at(1).P;
                    }
                }
            }
            else if (map[A_r][A_c].size() >= 1 && map[B_r][B_c].size() == 0) {
                answer += map[A_r][A_c].front().P;
            }
            else if (map[A_r][A_c].size() == 0 && map[B_r][B_c].size() >= 1) {
                answer += map[B_r][B_c].front().P;
            }
 
            //cout << m << " : " << result_A << " , " << result_B << endl;
            if (m == M)
                break;
 
            A_r += op[M_A[m]][0];
            A_c += op[M_A[m]][1];
            B_r += op[M_B[m]][0];
            B_c += op[M_B[m]][1];
        }
        cout << "#" << t << " " << answer << endl;
    }
    return 0;
}