SWEA 모의 역량 테스트 5644 무선 충전

SW Expert Academy

자료구조

• bc : BC들의 정보가 담긴 벡터 (P가 높은 순으로 정렬되어 있음)
• map : 각 칸은 벡터로 되어 있고, 해당 칸에서 사용 가능한 bc의 id가 담김 (자연스럽게 높은 순으로 정렬되어 있음)

풀이

1. sort() : BC들을 먼저 P가 높은 순으로 정렬한다

2. check_range() : 각 BC마다 BFS를 돌려서 방문하는 map의 벡터에 BC id를 넣어준다

   ⇒ P가 높은 BC부터 돌려주기 때문에 자연스럽게 각 칸에도 P가 높은 순으로 들어가게 되어 있음

3. 이제 m초간 시뮬레이션 : 각 칸의 벡터 크기로 조건을 나눠준다

   • A, B 한 명이 빈 칸에 있을 경우 (map[ay][ax].size()==0 || map[by][bx].size()==0)

     ⇒ 겹칠 일이 없으므로 size()가 0이 아닌 애의 sum만 증가시켜준다

   • 둘 다 size가 1인 칸에 있을 경우 (map[ay][ax].size()==1 && map[by][bx].size()==1)

     ⇒ 겹치면 p/2해서 증가

     ⇒ 안 겹치면 따로 증가

   • 한 쪽이 size()== 1 다른 쪽은 size()>1

     ⇒ 두 칸의 P 최댓값이 안 겹치면 그냥 따로 증가

     ⇒ 겹칠 경우, 선택권이 있는 애는 차선을 고를 수 있다 (A가 여러개면 bc[map[ay][ax][1]].p

     ⇒ 둘이 반씩 나누는 경우와 한 명이 양보하는 경우를 비교해서 넣어준다! (양보는 선택권이 넓은 애가)

   • 둘 다 size()>1

     ⇒ 반 씩 나누는 경우 / A가 양보하는 경우 / B가 양보하는 경우 중 최댓값을 적용

포인트

1. P순으로 bc들을 정렬해주는 것

2. 둘이 나눠쓰는 경우와 한 명이 양보하는 경우를 비교해주는 것

    

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
struct Pos{
    int y, x, cnt;
    Pos(int y, int x, int cnt):y(y), x(x), cnt(cnt) {};
};
struct BC{
    int y, x, c, p;
    BC(int y, int x, int c, int p):y(y), x(x), c(c), p(p) {};
};
int m, a;
int dy[]={0, -1, 0, 1, 0};
int dx[]={0, 0, 1, 0, -1};
vector<int> map[15][15];
int A[105];
int B[105];
vector<BC> bc;

bool op(BC a, BC b) {
    if(a.p >= b.p) return true;
    else return false;
}

void init() {
    for(int i=1; i<=10; i++) {
        for(int j=1; j<=10; j++) {
            map[i][j].clear();
        }
    }
    bc.clear();
}
void check_range(int idx) {
    int y = bc[idx].y; int x = bc[idx].x; int c = bc[idx].c;

    queue<Pos> q;
    int visit[15][15]; memset(visit, 0, sizeof(visit));
    q.push(Pos(y, x, 0));
    visit[y][x] = 1;
    while(!q.empty()) {
        y = q.front().y; x = q.front().x; int cnt = q.front().cnt;
        q.pop();
        map[y][x].push_back(idx);
        if(cnt==c) continue;
        for(int i=1; i<=4; i++) {
            int ny = y+dy[i]; int nx = x+dx[i];
            if(ny<1 || ny>10 || nx<1 || nx>10) continue;
            if(visit[ny][nx]) continue;

            visit[ny][nx] = 1;
            q.push(Pos(ny, nx, cnt+1));
        }
    }

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    for(int tc=1; tc<=T; tc++) {
        cin >> m >> a;
        for(int i=1; i<=m; i++) cin >> A[i];
        for(int i=1; i<=m; i++) cin >> B[i];

        for(int i=0; i<a; i++) {
            int y, x, c, p;
            cin >> x >> y >> c >> p;
            bc.push_back(BC(y, x, c, p));
        }
        sort(bc.begin(), bc.end(), op);

        // map에다가 표시
        for(int i=0; i<a; i++) {
            check_range(i);
        }

        int ay = 1, ax = 1, by=10, bx=10;
        int asum=0; int bsum=0;
        for(int i=0; i<=m; i++) {

            ay = ay + dy[A[i]]; ax = ax+dx[A[i]];
            by = by + dy[B[i]]; bx = bx+dx[B[i]];
            //cout<<i-1<<": "<<asum<<", "<<bsum<<endl;
            // 충전
            // 둘 중 하나가 충전범위가 아닐 경우
            if(map[ay][ax].size()==0 || map[by][bx].size()==0) {
                if(map[ay][ax].size()!=0) {
                    asum += bc[map[ay][ax][0]].p;
                }
                if(map[by][bx].size()!=0) {
                    bsum += bc[map[by][bx][0]].p;
                }
            }

            // 둘 다 한 개
            else if(map[ay][ax].size()==1 && map[by][bx].size()==1) {
                int id_a = map[ay][ax][0]; int id_b = map[by][bx][0];
                // 같은 BC
                if(id_a == id_b) {
                    asum += bc[id_a].p/2;
                    bsum += bc[id_b].p/2;
                }
                // 다른 BC
                else {
                    asum += bc[id_a].p;
                    bsum += bc[id_b].p;
                }
            }
            // b의 충전 범위가 여러 개 겹침
            else if(map[ay][ax].size()==1 && map[by][bx].size()>1){
                int id_a = map[ay][ax][0]; int id_b = map[by][bx][0];
                // a, b 안 겹침
                if(id_a != id_b) {
                    asum += bc[id_a].p;
                    bsum += bc[id_b].p;
                }
                // a, b의 최대 값 겹침
                else if(id_a == id_b) {
                    // 나누는게 값이 클 경우
                    if(bc[id_a].p/2 > bc[id_a].p + bc[map[by][bx][1]].p) {
                        asum += bc[id_a].p/2; bsum += bc[id_a].p/2;
                    }
                    else {
                        asum += bc[id_a].p;
                        bsum += bc[map[by][bx][1]].p;
                    }
                }
            }
            // a는 여러개 b는 한 개
            else if(map[ay][ax].size()>1 && map[by][bx].size()==1) {
                int id_a = map[ay][ax][0]; int id_b = map[by][bx][0];
                if(id_a != id_b) {
                    asum += bc[id_a].p;
                    bsum += bc[id_b].p;
                }
                else if(id_a == id_b) {
                    // 나누는게 값이 클 경우
                    if(bc[id_a].p/2 > bc[id_b].p + bc[map[ay][ax][1]].p) {
                        asum += bc[id_a].p/2;
                        bsum += bc[id_b].p/2;
                    }
                    else {
                        bsum += bc[id_b].p;
                        asum += bc[map[ay][ax][1]].p;
                    }
                }
            }
            // 둘 다 여러개
            else {
                int id_a = map[ay][ax][0]; int id_b = map[by][bx][0];
                // a, b 안 겹침
                if(id_a != id_b) {
                    asum += bc[id_a].p;
                    bsum += bc[id_b].p;
                }
                // a, b의 최대 값 겹침
                else if(id_a == id_b) {
                    int p, q, r;
                    p = bc[id_a].p;
                    q = bc[map[ay][ax][0]].p + bc[map[by][bx][1]].p;
                    r = bc[map[ay][ax][1]].p + bc[map[by][bx][0]].p;

                    if(p>=q && p>=r) {
                        asum += bc[id_a].p/2; bsum += bc[id_b].p/2;
                    }
                    else if(q>=p && q>=r) {
                        asum += bc[map[ay][ax][0]].p; bsum += bc[map[by][bx][1]].p;
                    }
                    else if(r>=p && r>=q) {
                        asum += bc[map[ay][ax][1]].p; bsum += bc[map[by][bx][0]].p;
                    }
                }
            }
        }
        cout<<'#'<<tc<<' '<<asum+bsum<<'\n';
        init();
    }

    return 0;
}