ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [SWEA] #5644 _ 무선 충전
    Problem Solving/SWEA 2019. 8. 4. 10:17
    728x90

    [무선 충전] https://swexpertacademy.com/main/code/problem/problemDetail.do

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

     

    bfs를 이용하여 BC의 충전 범위 만큼 성능 값을 맵에 저장한다.

    이 때, 사용자는 두명이기 때문에 BC의 가장 큰 두개의 값만 저장하고 있으면 된다.

    (BC가 4개가 겹칠 경우에 큰 성능 2개를 저장)

     

    미리 맵에 마름모 꼴로 성능 값을 저장해두고,

    두명의 사용자가 움직일 때, 맵에 저장된 값을 더해주면서 총 충전량을 구한다.

     

    [ 소스 코드 ]

    #include <cstdio>
    #include <queue>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    int dx[] = { 0, 0, 1, 0, -1 }, dy[] = { 0, -1, 0, 1, 0 };
    int user1[101], user2[101], p[9] = { 0, };
    int M, A;
    vector<vector<pair<int, int> > > map;
    
    void bfs(int bc, int x, int y, int c);
    int solve();
    int main() {
    	int test_case, x, y, c;
    	scanf("%d", &test_case);
    	for (int i = 1; i <= test_case; i++) {
    		scanf("%d %d", &M, &A);
    
    		map = vector<vector<pair<int, int> > >(11, vector<pair<int, int> >(11, make_pair(0, 0))); // Init map
    		for (int j = 0; j < M; j++) scanf("%d", &user1[j]); // Input user1 data
    		for (int j = 0; j < M; j++) scanf("%d", &user2[j]); // Input user2 data
    		for (int j = 1; j <= A; j++) { // Input BC data
    			scanf("%d %d %d %d", &x, &y, &c, &p[j]);
    			bfs(j, x-1, y-1, c);
    		}
    		printf("#%d %d\n", i, solve()); // Print result
    	}
    	return 0;
    }
    
    void bfs(int bc, int x, int y, int c) { // Marking chargeable area
    	int check[11][11] = { 0, }, p_count = 0;
    	queue<pair<int, int> > q;
    	pair<int, int> tmp;
    
    	q.push(make_pair(x, y));
    
    	while (!q.empty()) {
    		tmp = q.front();
    		q.pop();
    		if (map[tmp.second][tmp.first].first == 0) map[tmp.second][tmp.first].first = bc;
    		else if (map[tmp.second][tmp.first].first != bc && map[tmp.second][tmp.first].second == 0) {
    			if (p[map[tmp.second][tmp.first].first] < p[bc]) {
    				map[tmp.second][tmp.first].second = map[tmp.second][tmp.first].first;
    				map[tmp.second][tmp.first].first = bc;
    			}
    			else map[tmp.second][tmp.first].second = bc;
    		}
    		else if (map[tmp.second][tmp.first].first != bc && map[tmp.second][tmp.first].second != bc) {
    			if (p[map[tmp.second][tmp.first].first] < p[bc]) {
    				map[tmp.second][tmp.first].second = map[tmp.second][tmp.first].first;
    				map[tmp.second][tmp.first].first = bc;
    			}
    			else if (p[map[tmp.second][tmp.first].second] < p[bc]) {
    				map[tmp.second][tmp.first].second = bc;
    			}
    		}
    
    		for (int i = 1; i <= 4; i++) {
    			x = tmp.first + dx[i];
    			y = tmp.second + dy[i];
    
    			if (x < 0 || y < 0 || x > 10 || y > 10) continue;
    			if (check[tmp.second][tmp.first] >= c) continue;
    			if (check[y][x] != 0) continue;
    			q.push(make_pair(x, y));
    			check[y][x] = check[tmp.second][tmp.first] + 1;
    		}
    	}
    }
    
    int solve() {
    	int u1_x = 0, u1_y = 0, u2_x = 9, u2_y = 9;
    	int total = p[map[u1_y][u1_x].first] + p[map[u2_y][u2_x].first];
    	for (int i = 0; i < M; i++) {
    		u1_x += dx[user1[i]]; // Move user1
    		u1_y += dy[user1[i]];
    		u2_x += dx[user2[i]]; // Move user2
    		u2_y += dy[user2[i]];
    		if (map[u1_y][u1_x].first == map[u2_y][u2_x].first) // if Same area
    			total += max(p[map[u1_y][u1_x].first] + p[map[u1_y][u1_x].second], p[map[u2_y][u2_x].first] + p[map[u2_y][u2_x].second]);
    		else total += p[map[u1_y][u1_x].first] + p[map[u2_y][u2_x].first];
    	}
    
    	return total;
    }
    반응형

    'Problem Solving > SWEA' 카테고리의 다른 글

    [SWEA] #1209 _ Sum  (0) 2019.08.12
    [SWEA] #5656 _ 벽돌 깨기  (0) 2019.08.04
    [SWEA] #5644 _ 무선 충전  (0) 2019.08.04
    [SWEA] #5215 _ 햄버거 다이어트  (0) 2019.08.04
    [SWEA] #2805 _ 농작물 수확하기  (0) 2019.08.04
    [SWEA] #1215 _ 회문1  (0) 2019.08.04

    댓글 0

@Jo Grini's Blog