5644.무선충전

이번에 풀어볼 문제는 SW Expert의 5644 무선충전이다. ( 아래링크는 SW Expert 로그인하고 눌러야함.. )

SW Expert Academy

결론은 설계실패로 문제를 풀지 못했다 => 다른분의 블로그를 참조하여 공부함 : https://swjeong.tistory.com/162

3시간을 초과했고 설계실패의 이유는 한가지를 간과했다.

 

---

< 나의 설계 및 접근 >

 

1. BC의 범위를 배열에 표시했다.

 

2. A사용자와 B사용자가 중복되는 구간을 따로 배열을 만들어 표시했다.

 

3. 중복구간을 제외한 나머지 구간의 합을 구했다. 

 

4. 설계 실패가 발생한 지점 => 중복구간에서 어떤 BC들이 중복되는지를 표시하지않아서 정확한 최대값을 구할수가 X

   => 문제에서 주어진 BC에 충전할 수 있는 범위에 대한 내용을 무시한 것이 설계 실패의 요인..

   => 물론 계속하면 언젠가는 BC를 구별하는 로직을 생각해내겠지만 이미 시간이 늦어버렸다..

 

5. 결과 : 테스트케이스 5개중 2개만 정답.. (조... 짓... 다...)

 

#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <string.h>
 
#define MAX 11
 
using namespace std;
 
int T, M, A;
 
int dx[5] = { 0, -1, 0, 1, 0 }; // 제자리, 상, 우, 하 좌
int dy[5] = { 0, 0, 1, 0, -1 };
 
int cx[4] = { 0, 0, 1, -1 };
int cy[4] = { 1, -1, 0, 0 };
 
int a_start_x = 1, a_start_y = 1;
int b_start_x = 10, b_start_y = 10;
 
 
queue<pair<int, int>>a;
queue<pair<int, int>>b;
 
 
int check[MAX][MAX];
int bc_map[MAX][MAX]; //BC의 형태파악
int dup[MAX][MAX]; // 중복구간 파악
int tt[MAX][MAX];
 
void mov_a(int d){
    a_start_x += dx[d];
    a_start_y += dy[d];
    a.push(make_pair(a_start_x, a_start_y));
}
 
void mov_b(int d){
    b_start_x += dx[d];
    b_start_y += dy[d];
    b.push(make_pair(b_start_x, b_start_y));
}
 
void reset(){
    a_start_x = a_start_y = 1;
    b_start_x = b_start_y = 10;
    int size = a.size();
    for (int i = 0; i < size; i++){
        a.pop();
        b.pop();
    }
    a.push(make_pair(a_start_x, a_start_y));
    b.push(make_pair(b_start_x, b_start_y));
    memset(check, 0, sizeof(check));
    memset(bc_map, 0, sizeof(bc_map));
    memset(dup, 0, sizeof(dup));
}
 
queue<pair<int, int>>bc;
 
void make_bc(int aa, int bb, int len, int power){
    bc.push(make_pair(aa, bb));
    bc_map[aa][bb] = power;
    tt[aa][bb] = power;
    while (!bc.empty()){
        int x = bc.front().first;
        int y = bc.front().second;
        bc.pop();
        if (check[x][y] == len)
            break;
        for (int i = 0; i < 4; i++){
            int ax = x + cx[i];
            int ay = y + cy[i];
            if (ax < 0 || ay < 0 || ax >= MAX || ay >= MAX)
                continue;
            if (!check[ax][ay]){
                if (bc_map[ax][ay] != 0 && bc_map[ax][ay] != power){
                    dup[ax][ay] = bc_map[ax][ay] + power; // 둘이 합한값으로 저장
                    tt[ax][ay] = 0;
                }
                else
                    tt[ax][ay] = power;
 
                check[ax][ay] = check[x][y] + 1;
                bc_map[ax][ay] = power;
                bc.push(make_pair(ax, ay));
            }
        }
    }
    memset(check, 0, sizeof(check));
    int size = bc.size();
    for (int i = 0; i < size; i++)
        bc.pop();
}
 
 
void go_work(){
    int ans = 0;
    while (!a.empty()){
        int a_xx = a.front().first;
        int a_yy = a.front().second;
        int b_xx = b.front().first;
        int b_yy = b.front().second;
        if (!dup[a_xx][a_yy] && bc_map[a_xx][a_yy]){
 
            ans += tt[a_xx][a_yy];
        }
        
        if (!dup[b_xx][a_yy] && bc_map[b_xx][b_yy])
            ans += bc_map[b_xx][b_yy];
 
        a.pop();
        b.pop();
    }
    cout << ans << endl;
}
 
int main(){
    freopen("5644_sw.txt", "r", stdin);
    cin >> T;
    for (int z = 0; z < T; z++){
        reset(); // 다음 테스트케이스를 위한 초기화
        cin >> M >> A;
        int tmp;
        // 경로 입력받기
        for (int i = 0; i < M; i++){ // 사용자 A의 경로
            cin >> tmp;
            mov_a(tmp);
        }
        for (int i = 0; i < M; i++){ // 사용자 B의 경로
            cin >> tmp;
            mov_b(tmp);
        }
        // BC 만들기
        int bc_x, bc_y, len, power;
        for (int i = 0; i < A; i++){ // A = AP 갯수
            cin >> bc_y >> bc_x >> len >> power;
            make_bc(bc_x, bc_y, len, power);
        }
        go_work();
    }
    return 0;
}

 

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <string.h>
 
using namespace std;
 
struct bc{
    int x;
    int y;
    int len;
    int pwr;
};
 
int dx[5] = {0,-1,0,1,0}; // 정지, 위, 오른쪽, 아래, 왼쪽
int dy[5] = {0,0,1,0,-1};
 
int T, M, A;
 
int mov[2][101]; // A와 B의 이동경로가 저장되는 2차원 배열
 
vector<bc>v; // BC의 정보가 저장되는 vector
 
int go_work(){
    int a_x =1, a_y = 1;   // A사용자의 시작좌표
    int b_x =10, b_y = 10; // B사용자의 시작좌표
    int answer_A = 0, answer_B = 0; //1초에 충전되는 A사용자의 충전량,  B사용자의 충전량
 
    for (int z = 0; z <=M; z++){ // 이동하는 시간 기간
        vector<int>a; // 사용자A의 경로에 포함되는 BC 번호 저장
        vector<int>b; // 사용자B의 경로에 포함되는 BC 번호 저장
        for (int i = 0; i < A; i++){
            if (abs(a_x - v[i].x) + abs(a_y - v[i].y) <= v[i].len) // A의 경로중에 BC의 범위내에 들어가면
                a.push_back(i); // BC 번호저장
 
            if (abs(b_x - v[i].x) + abs(b_y - v[i].y) <= v[i].len) // B의 경로중에 BC의 범위내에 들어가면
                b.push_back(i); // BC 번호저장
        }
 
        int tmp = 0, a_sum = 0, b_sum = 0; 
        if (!a.empty() && b.empty()){ // A만 BC의 범위 내부를 지나 충전하는 경우 && B는 BC범위 밖에 있음(B는 충전x)
            for (int j = 0; j < a.size(); j++){ // A의 경로에 저장된 BC들 중에
                int power = v[a[j]].pwr; // 저장된 BC의 power값 사용
                if (tmp < power){ // BC의 power값들 중 
                    tmp = power;  // 최대값을 찾음
                    a_sum = power;// A사용자만 통과하는 BC power 사용
                }
            }
        }
        else if (a.empty() && !b.empty()){ // B만 BC의 범위 내부를 지나 충전하는 경우 && A는 BC범위 밖에 있음(A는 충전x)
            for (int j = 0; j < b.size(); j++){ // B의 경로에 저장된 BC들 중에
                int power2 = v[b[j]].pwr; // 저장된 BC의 power값을 사용
                if (tmp < power2){ // BC의 power값들 중
                    tmp = power2;  // 최대값을 찾음
                    b_sum = power2;// B사용자만 통과하는 BC power 사용
                }
            }
        }
        else { // A와 B둘다 BC를 지나 충전하는 경우
            for (int j = 0; j < a.size(); j++){  
                for (int w = 0; w < b.size(); w++){
                    int power1 = v[a[j]].pwr;  // A가 지나는 BC의 power
                    int power2 = v[b[w]].pwr;  // B가 지나는 BC의 power 
                    if (a[j] == b[w]){ // A와 B가 같은 BC 범위 내부를 지나면 ( 충전량을 나누어씀 )
                        power1 /= 2; // A의 BC 충전량은 반값이다.
                        power2 /= 2; // B의 BC 충전량은 반값이다.
                    }
                    if (tmp < power1 + power2){ // 둘다 BC를 지나 충전을 하지만 겹치는 범위는 아닌경우
                        tmp = power1 + power2; // 최대값을 사용한다.
                        a_sum = power1; // A가 충전하는 BC의 power
                        b_sum = power2; // B가 충전하는 BC의 power
                    }
                }
            }
        }
        a_x += dx[mov[0][z]]; // A사용자의 다음 x좌표로 이동
        a_y += dy[mov[0][z]]; // A사용자의 다음 y좌표로 이동
        b_x += dx[mov[1][z]]; // B사용자의 다음 x좌표로 이동
        b_y += dy[mov[1][z]]; // B사용자의 다음 y좌표로 이동
        answer_A += a_sum; // A 충전한 값 누산
        answer_B += b_sum; // B 충전한 값 누산
    }
    return answer_A + answer_B; // A와 B 충전한 값 리턴
}
 
 
int main(){
    freopen("5644_sw.txt", "r", stdin);
    cin >> T;
    for (int k = 1; k <= T; k++){
        memset(mov[0], 0, sizeof(mov[0]));
        memset(mov[1], 0, sizeof(mov[1]));
        v.clear();
        cin >> M >> A;
        for (int i = 0; i < M; i++) // B사용자의 이동경로 저장
            cin >> mov[0][i];
        
        for (int i = 0; i < M; i++) // A사용자의 이동경로 저장 
            cin >> mov[1][i];
        
        int bc_x, bc_y, bc_len, bc_pwr;
        for (int i = 0; i < A; i++){
            cin >> bc_y >> bc_x >> bc_len >> bc_pwr; // BC의 x,y좌표, 범위, 파워 입력받음
            v.push_back({ bc_x, bc_y, bc_len, bc_pwr });
        }
        cout << "#" << k << " " << go_work() << "\n";    
    }
 
    return 0;
}

# 오늘의 결론도 역시.. 설계를 꼼꼼히 하자!!

---

나의 설계와의 차이점과 로직

굳이 필요없는 BC의 범위를 다 구하지 않는다 => 나는 예시 그림처럼 다구했는데.. 흠... 굳이 그럴 필요가 없다.

---

 

* 1초 기준이 반복 *

0. vector에 BC의 정보를 모두 입력받음.

1.  A사용자의 좌표와 vector의 BC 좌표와의 거리를 비교하여 각각의 사용자가 BC 범위내에 충전중인지 확인하고

   사용중이라면 해당 vector의 번호(BC정보)를 queue에 각각 저장(A사용자, B사용자)
    

 

2. BC 범위내에서 충전중이라면 해당 queue는 비어있지 않는다는 점을 이용하여 A사용자만 충전되는 경우와

   B사용자만 충전되는 경우를 나눠서 최대값으로 power값을 누산 ( 저장 시에는 최대값을 비교해서 저장함 ) 

 

 

 

3. 마지막으로 A사용자와 B사용자 둘다 BC를 지나는 경우를 생각해보자.

   둘다 지나는 경우는 두 가지다. 같은 BC를 지나는 경우 => 이 때는 그냥 서로 반값을 사용하면된다.

   각자 다른 BC를 지나는 경우 => 이 때도 각자의 BC power를 더해주면된다.

   그렇다면 하나가 중복구간을 지나는 경우라면??? => 이 경우는 생각해줄 필요가 없다.

   이유는 이중for문을 통해 BC를 지날 수 있는 경우의 수를 모두 비교했고 그중에서 중복구간에 대한 연산도

   최대값으로 처리 저장할 때 완료되기때문이다.