SWEA 5644번 - 무선충전

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

구현하는게 생각보다 까다로운 문제다.

문제에 제시된 변수가 많아서 코드를 깔끔하게 짜지 못한 것 같아서 아쉬운데

우선 접근 방향은 다음과 같다.

1) A,B의 이동 경로와 설치된 BC의 좌표 및 거리,충전량을 입력받는다

2) 각각의 BC를 현재 좌표에서 거리가 닿는 만큼 좌표마다 BC번호와 충전량을 저장해준다.

   (지도의 y,x좌표에 각각 BC번호와 충전량을 insert 해주는 방식)

3)초기의 A,B 좌표에서 이동을 시작하며 각각의 좌표에 저장된 BC 정보에 따라 충전량을 더해준다

위의 방식대로 구현할 때

좌표마다 BC번호와 충전량을 저장해주기 위해 vector<pair<int,int>> 형식으로 좌표를 구성했다. 

그리고 거리가 닿는 만큼 충전량을 저장해주기 위해 큐를 이용해서 거리 순서대로 충전량을 저장해주면 된다.

주의할 점은 이동을 하지 않은 초기 좌표에서의 충전량을 계산해야 하기 때문에

이동을 하기전인 0부터 이동 순서인 M만큼 충전량을 구해줘야 한다. 즉, M+1번 충전량을 계산해주면 된다.

마지막으로 A,B의 좌표에서 충전량의 최대값을 구할 때

동일한 BC번호일 때 2만큼 나눠줘야 올바른 충전량을 구할 수 있다.

#include <iostream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
#define N 10
 
struct str{
    int y;
    int x;
    int c;
    int p;
    str(int y,int x,int c,int p):y(y),x(x),c(c),p(p){};
};
 
int M,A;
vector<pair<int,int>> map[N][N]; //(y,x) 좌표에서 make_pair(BC번호, 충전량)
vector<int> move_A; //A의 이동 방향
vector<int> move_B; //B의 이동 방향
vector<str> BC;
int dy[5]={0,-1,0,1,0};
int dx[5]={0,0,1,0,-1};
 
//BC 충전 범위 계산
void cal_bc(){
    
    for(int i=0;i<A;i++){
        
        str s=BC[i];
        vector<vector<int>> visited(N,vector<int>(N,0));
        
        visited[s.y][s.x]++;
        queue<str> q;
        q.push(s);
        
        while(!q.empty()){
            
            int y=q.front().y;
            int x=q.front().x;
            int c=q.front().c;
            int p=q.front().p;
            q.pop();
            
            if(c<0)
                continue;
            
            map[y][x].push_back(make_pair(i,p)); //y,x좌표의 BC번호(i)와 충전량 삽입
            for(int dir=1;dir<=4;dir++){
                int ny=y+dy[dir];
                int nx=x+dx[dir];
                
                if(ny<0 || ny>=N || nx<0 || nx>=N)
                    continue;
                
                if(visited[ny][nx])
                    continue;
                
                visited[ny][nx]++;
                q.push(str(ny,nx,c-1,p));
            }
            
        }
        
    }
    
}
 
//이동에 따른 충전량의 합 구하기
int cal_move(){
    
    int y1=0,x1=0; //A의 y,x좌표
    int y2=N-1,x2=N-1; //B의 y,x좌표
    int ans=0;
 
    for(int i=0;i<=M;i++){ //이동하지 않을 때 계산하기 위해 0부터 시작
        
        int sum=0;
        if(map[y1][x1].size()==0){ //A좌표 비어 있을 때
            for(int j=0;j<map[y2][x2].size();j++)
                sum=max(sum,map[y2][x2][j].second);
        }
        else if(map[y2][x2].size()==0){ //B좌표 비어 있을 때
            for(int j=0;j<map[y1][x1].size();j++)
                sum=max(sum,map[y1][x1][j].second);
        }
        else if(map[y1][x1].size()>0 && map[y2][x2].size()>0){
            
            for(int j=0;j<map[y1][x1].size();j++)
                for(int k=0;k<map[y2][x2].size();k++){
                    
                    int bc1=map[y1][x1][j].first;
                    int bc2=map[y2][x2][k].first;
                    int p1=map[y1][x1][j].second;
                    int p2=map[y2][x2][k].second;
                    
                    if(bc1==bc2)
                        sum=max(sum,(p1+p2)/2);
                    else
                        sum=max(sum,p1+p2);
                }
 
            
        }
        
        ans+=sum;
        
        if(i<M){
            y1+=dy[move_A[i]];
            x1+=dx[move_A[i]];
            y2+=dy[move_B[i]];
            x2+=dx[move_B[i]];
        }
    }
 
    return ans;
}
 
int main(){
    
    int T;
    cin>>T;
    
    for(int testCase=1;testCase<=T;testCase++){
        
        scanf("%d %d",&M,&A);
        
        for(int i=0;i<N;i++)
            for(int j=0;j<N;j++)
                map[i][j].clear();
        
        move_A=vector<int> (M,0);
        move_B=vector<int> (M,0);
        BC.clear();
        
        for(int i=0;i<M;i++)    scanf("%d",&move_A[i]);
        for(int i=0;i<M;i++)    scanf("%d",&move_B[i]);
        
        for(int i=1;i<=A;i++){
            int x,y,c,p;
            scanf("%d %d %d %d",&x,&y,&c,&p);
            BC.push_back(str(y-1,x-1,c,p));
        }
        
        cal_bc();
        cout<<"#"<<testCase<<" "<<cal_move()<<endl;
    }
    
    return 0;
}