SWEA5644 [모의 SW 역량테스트] 무선 충전 C++

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE&problemTitle=모의&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1&&&&&&&&& 

 

최종 코드

• GitHub -> https://github.com/hwayeon351/SWEA-Algorithms/blob/main/SWEA5644.cpp

GitHub - hwayeon351/SWEA-Algorithms: SWEA 알고리즘 소스 코드 모음

//
//  main.cpp
//  SWEA5644
//
//  Created by Hwayeon on 2021/10/20.
//

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

int M, A;
int map[11][11][8] = {0, };
int dx[5] = {0, 0, 1, 0, -1};
int dy[5] = {0, -1, 0, 1, 0};
struct User{
    int x;
    int y;
    int dir[100] = {0, };
};
struct BatteryCharger{
    int x;
    int y;
    int C;
    int P;
};
BatteryCharger bc;
vector<BatteryCharger> BC;
vector<User> users;
vector<int> A_choice;
vector<int> B_choice;
int total_charge = 0;

void get_BC_area(){
    for(int i=0; i<A; i++){
        bc = BC[i];
        queue<pair<pair<int, int>, int>> q;
        q.push({{bc.x, bc.y}, 0});
        map[bc.y][bc.x][i] = 1;
        while(!q.empty()){
            int x = q.front().first.first;
            int y = q.front().first.second;
            int cnt = q.front().second;
            q.pop();
            if(cnt >= bc.C) break;
            for(int d=1; d<5; d++){
                int nx = x + dx[d];
                int ny = y + dy[d];
                if(nx<1 || nx>10 || ny<1 || ny>10) continue;
                if(map[ny][nx][i]) continue;
                map[ny][nx][i] = 1;
                q.push({{nx, ny}, cnt+1});
            }
        }
    }
}

int get_choice(){
    A_choice.clear();
    B_choice.clear();
    for(int a=0; a<A; a++){
        if(map[users[0].y][users[0].x][a]){
            A_choice.push_back(a);
        }
        if(map[users[1].y][users[1].x][a]){
            B_choice.push_back(a);
        }
    }
    int now_charge = 0;
    if(A_choice.empty()){
        for(int b=0; b<B_choice.size(); b++){
            if(now_charge < BC[B_choice[b]].P) now_charge = BC[B_choice[b]].P;
        }
    }
    else if(B_choice.empty()){
        for(int a=0; a<A_choice.size(); a++){
            if(now_charge < BC[A_choice[a]].P) now_charge = BC[A_choice[a]].P;
        }
    }
    else{
        for(int a=0; a<A_choice.size(); a++){
            for(int b=0; b<B_choice.size(); b++){
                int charge = 0;
                if(A_choice[a] == B_choice[b]){
                    charge = BC[A_choice[a]].P;
                }
                else{
                    charge = BC[A_choice[a]].P + BC[B_choice[b]].P;
                }
                if(now_charge < charge) now_charge = charge;
            }
        }
    }
    return now_charge;
}

void move_users(){
    total_charge = get_choice();
    for(int i=0; i<M; i++){
        for(int j=0; j<2; j++){
            users[j].x += dx[users[j].dir[i]];
            users[j].y += dy[users[j].dir[i]];
        }
        total_charge += get_choice();
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
        memset(map, 0, sizeof(map));
        total_charge = 0;
        BC.clear();
        users.clear();
        User user;
        user.x = 1;
        user.y = 1;
        users.push_back(user);
        user.x = 10;
        user.y = 10;
        users.push_back(user);
        
        cin >> M >> A;
        for(int i=0; i<2; i++){
            for(int j=0; j<M; j++){
                cin >> users[i].dir[j];
            }
        }
        for(int i=0; i<A; i++){
            cin >> bc.x >> bc.y >> bc.C >> bc.P;
            BC.push_back(bc);
        }
        get_BC_area();
        move_users();
        cout << "#" << test_case << " " << total_charge << endl;
    }
    return 0;
}

---

풀이 과정

풀이 시간 1시간 23분

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

int M, A;

//map[y][x][i] = 1 -> (x, y)에서 i번째 BC에 접속할 수 있는 경우
//map[y][x][i] = 0 -> (x, y)에서 i번째 BC에 접속할 수 없는 경우
int map[11][11][8] = {0, };

//0-그대로, 1-상, 2-우, 3-하, 4-좌
int dx[5] = {0, 0, 1, 0, -1};
int dy[5] = {0, -1, 0, 1, 0};

struct User{
	//현재 위치
    int x;
    int y;
    //이동 정보
    int dir[100] = {0, };
};

struct BatteryCharger{
	//BC 위치
    int x;
    int y;
    //충전 범위
    int C;
    //처리량
    int P;
};
BatteryCharger bc;

//BC들을 담는 벡터
vector<BatteryCharger> BC;
//사용자들을 담는 벡터
vector<User> users;

//A 사용자의 BC 선택권을 담는 벡터
vector<int> A_choice;
//B 사용자의 BC 선택권을 담는 벡터
vector<int> B_choice;

int total_charge = 0;

void get_BC_area(){
	//모든 BC에 대해 진행
    for(int i=0; i<A; i++){
        bc = BC[i];
        queue<pair<pair<int, int>, int>> q;
        //위치, bc의 위치로부터의 거리
        q.push({{bc.x, bc.y}, 0});
        map[bc.y][bc.x][i] = 1;
        
        while(!q.empty()){
            int x = q.front().first.first;
            int y = q.front().first.second;
            int cnt = q.front().second;
            q.pop();
            //범위를 벗어난 경우, bfs 탐색을 종료한다
            if(cnt >= bc.C) break;
            for(int d=1; d<5; d++){
                int nx = x + dx[d];
                int ny = y + dy[d];
                
                //지도를 벗어난 경우, 무시한다
                if(nx<1 || nx>10 || ny<1 || ny>10) continue;
                //이미 처리한 위치인 경우, 무시한다
                if(map[ny][nx][i]) continue;
                
                //bc의 충전 영역을 표시한다
                map[ny][nx][i] = 1;
                q.push({{nx, ny}, cnt+1});
            }
        }
    }
}

int get_choice(){
    A_choice.clear();
    B_choice.clear();
    
    //각 사용자들이 해당 위치에서 선택할 수 있는 BC를 구한다
    for(int a=0; a<A; a++){
        if(map[users[0].y][users[0].x][a]){
            A_choice.push_back(a);
        }
        if(map[users[1].y][users[1].x][a]){
            B_choice.push_back(a);
        }
    }
    
    int now_charge = 0;
    
    //사용자 A는 충전할 수 없고, 사용자 B만 충전 가능한 경우
    if(A_choice.empty()){
    	//가장 많은 처리량을 가진 BC를 선택한다
        for(int b=0; b<B_choice.size(); b++){
            if(now_charge < BC[B_choice[b]].P) now_charge = BC[B_choice[b]].P;
        }
    }
    //사용자 B는 충전할 수 없고, 사용자 A만 충전 가능한 경우
    else if(B_choice.empty()){
    	//가장 많은 처리량을 가진 BC를 선택한다
        for(int a=0; a<A_choice.size(); a++){
            if(now_charge < BC[A_choice[a]].P) now_charge = BC[A_choice[a]].P;
        }
    }
    //둘 다 충전할 수 있는 경우,
    else{
    	//선택지의 모든 조합을 탐색하여 최대 충전량을 구한다
        for(int a=0; a<A_choice.size(); a++){
            for(int b=0; b<B_choice.size(); b++){
                int charge = 0;
                //두 사용자가 같은 BC를 선택한 경우, 해당 BC의 처리량을 균등하게 나누어 가진다
                if(A_choice[a] == B_choice[b]){
                    charge = BC[A_choice[a]].P;
                }
                //두 사용자가 서로 다른 BC를 선택한 경우,
                else{
                    charge = BC[A_choice[a]].P + BC[B_choice[b]].P;
                }
                //now_charge를 최대값으로 갱신한다
                if(now_charge < charge) now_charge = charge;
            }
        }
    }
    return now_charge;
}

void move_users(){
	//0초에서 충전을 진행한다
    total_charge = get_choice();
    
    //1초마다 사용자를 이동시킨다
    for(int i=0; i<M; i++){
        for(int j=0; j<2; j++){
            users[j].x += dx[users[j].dir[i]];
            users[j].y += dy[users[j].dir[i]];
        }
        //해당 시간에 충전할 수 있는 최대 경우를 total_charge에 더해준다
        total_charge += get_choice();
    }
}

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    for(test_case=1; test_case<=T; ++test_case){
    	//초기화
        memset(map, 0, sizeof(map));
        total_charge = 0;
        BC.clear();
        users.clear();
        User user;
        user.x = 1;
        user.y = 1;
        users.push_back(user);
        user.x = 10;
        user.y = 10;
        users.push_back(user);
        
        cin >> M >> A;
        for(int i=0; i<2; i++){
            for(int j=0; j<M; j++){
                cin >> users[i].dir[j];
            }
        }
        for(int i=0; i<A; i++){
            cin >> bc.x >> bc.y >> bc.C >> bc.P;
            BC.push_back(bc);
        }
        
        //각 BC들의 충전 범위가 미치는 영역을 구한다
        get_BC_area();
        
        //사용자들을 이동시키면서 충전한다
        move_users();
        
        cout << "#" << test_case << " " << total_charge << endl;
    }
    return 0;
}