•
문제의 저작권은 SWEA에 있습니다.
문제
1.
지도에는 N개의 충전소가 존재
a.
각 충전소는 충전 범위, 성능이 존재
2.
A, B 두사람이 은 각각 (1,1), (10,10)에서 출발하여 동시에 한번씩 이동함
3.
매 이동 횟수마다 근처의 충전소를 통해 충전을 함
a.
현재 위치가 근처 충전소의 충전 범위 내에 있을 시 충전
b.
만약 한개의 충전소를 여러명이 동시에 접속하면 나누어서 충전함 (각각 성능 / 2)
c.
선택 가능한 충전소의 선택지가 여러개인 경우 최대한 많은 충전을 할 수 있는 충전소를 선택
4.
모든 이동을 마쳤을 때 모든 사용자가 충전한 양의 합의 최대값을 구해서 출력
풀이
전형적인 시뮬레이션 문제이다.
크게 2가지 풀이 방법으로 접근할 수 있다.
1.
사람이 이동하면서 현재 위치에서 접속할 수 있는 충전소들을 찾기
2.
전체 지도에 충전소를 미리 배치하고 해당 위치에 도달하면 가져다 쓰기
2번 풀이로 해설을 진행.
1.
전체 지도에 충전소를 배치하기 위해 각 충전소에 대해 BFS를 수행하며 충전 영역 범위 내에 있는 곳에 충전소를 배치
a.
2차원 배열 지도에 충전소를 배치하기 위해 2차원 배열을 vector<pair<int,int>>
형태로 선언해주었다.
b.
2차원 배열 특정 좌표에 충전소를 배치하는 경우 {power, 충전소 index} 형태로 push_back
c.
map[ i ][ j ].size()를 통해 현재 위치의 충전소의 개수를 알 수 있다.
2.
매번 이동을 하면서 해당 좌표에 있는 충전소를 이용해 충전을 하기
⇒ 충전을 할 때 고려해주어야 하는 Case가 있다.
a.
A는 충전을 못시키고 B는 충전을 시킬 수 있는 경우
→ B 위치에 있는 충전소 중 power가 제일 큰 값 사용
b.
A는 충전을 시키고 B는 충전을 못시키는 경우
→ A 위치에 있는 충전소 중 power가 제일 큰 값 사용
c.
A와 B 둘 다 충전을 시킬 수 있는 경우
c-1. A 위치의 충전소의 개수와 B 위치의 충전소의 개수가 둘 다 1개이면서, 같은 충전소일 때
⇒ A, B 는 한 충전소를 나누어 가져야 한다.
c-2. A 와 B가 서로 다른 충전소를 사용할 수 있는 경우
⇒ A, B가 가지고 있는 충전소로 충전할 수 있는 모든 경우의 수를 구하고, 그 중 최대값을
선택한다.
3.
이동이 모두 끝난 후 충전량의 합을 출력한다.
기본적인 문제 요구사항에 충실하면서, 주어진 상황에 따라 if-else를 통해 적절히 조건을 분기하면 된다. c 조건의 구현 방법은 여러개가 존재한다.
1.
A 충전기 == 1 && B 충전기 > 1 → B 충전기의 2번째 큰 값 사용하는 식으로 조건 분기하기
2.
가능한 모든 경우의 수 구하고 최소값
1번 방법은 2번째로 큰 값을 구하기 위한 sort 과정과 i - 1 인덱스 접근의 oob 에러를 방지하기 위한 조건 분기가 많이 발생하여 코드가 복잡하게 된다.
따라서 2번 방법을 선택하여 풀이를 진행하였다.
•
setting() 함수
- BFS를 통해 map을 탐색하며, 지도에 충전소를 배치
void setting() {
for (int i = 0; i < bc_num; i++) {
bfs(chargers[i], i); // i번째 충전소에 대해 BFS 수행
}
}
void bfs(charger bc, int bcNum) { // 충전 범위 내에서 퍼져나감
queue<pii> q;
bool visit[11][11] = { 0 };
visit[bc.x][bc.y] = 1;
arr[bc.x][bc.y].push_back({ bc.p,bcNum });
q.push({ bc.x, bc.y });
int cnt = 1;
while (!q.empty()) {
int size = q.size();
while (size-- > 0) {
auto [cur_x, cur_y] = q.front(); q.pop();
for (int i = 0; i < 5; i++) {
int nx = cur_x + dx[i];
int ny = cur_y + dy[i];
if (!oob(nx, ny) && !visit[nx][ny]) {
visit[nx][ny] = true;
arr[nx][ny].push_back({ bc.p, bcNum }); // 충전범위 내의 좌표에 충전소 추가
q.push({ nx, ny });
}
}
}
if (cnt == bc.c) break;
cnt++;
}
}
C++
복사
•
solve() 함수
- 특정 좌표에서 A, B가 충전할 수 있는 충전량의 최대값을 return
int solve() {
int sum = 0;
int a_size = arr[a_x][a_y].size();
int b_size = arr[b_x][b_y].size();
if (a_size == 0) { // B만 충전시킬 수 있는 경우 -> B의 충전소 중 최대값
for (int i = 0; i < b_size; i++)
sum = max(sum, arr[b_x][b_y][i].fst);
}else if (b_size == 0) { // A만 충전시킬 수 있는 경우 -> B의 충전소 중 최대값
for (int i = 0; i < a_size; i++)
sum = max(sum, arr[a_x][a_y][i].fst);
}else { // A, B 모두 충전시킬 수 있는 경우 -> 모든 조합 중 최대
for (int i = 0; i < a_size; i++) {
for (int j = 0; j < b_size; j++) {
if (arr[a_x][a_y][i].snd == arr[b_x][b_y][j].snd) // 만약 두개 충전소가 겹치면
sum = max(sum, arr[a_x][a_y][i].fst); // 하나로 두명이 나눠쓰기
else
sum = max(sum, arr[a_x][a_y][i].fst + arr[b_x][b_y][j].fst); //겹치지않으면 각각
}
}
}
return sum;
}
C++
복사
•
Main 함수 동작
int main() {
fastio;
txtcin;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> mv >> bc_num;
init();
for (int i = 0; i < mv; i++) {
cin >> a;
a_dir.push_back(a);
}
for (int i = 0; i < mv; i++) {
cin >> a;
b_dir.push_back(a);
}
for (int i = 0; i < bc_num; i++) {
int y, x, c, p;
cin >> y >> x >> c >> p;
charger temp = { x,y,c,p };
chargers.push_back(temp);
}
setting(); // BFS를 통한 지도 세팅
int answer = 0; // 최종 정답 저장
answer += solve();
for (int i = 0; i < mv; i++) { // A, B가 mv번 이동하면서 좌표 변경
a_x += dx[a_dir[i]];
a_y += dy[a_dir[i]];
b_x += dx[b_dir[i]];
b_y += dy[b_dir[i]];
answer += solve(); // A,B 각 좌표에 대해 충전량 구하기 수행
}
cout << "#" << tc << " " << answer << endl;
}
return 0;
}
C++
복사
