[SWEA] #5644 _ 무선 충전

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

SW Expert Academy

 

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;
}