20056번: 마법사 상어와 파이어볼
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치
www.acmicpc.net
1. 풀이방법
- 구현 문제이고 문제풀이에 필요한 알고리즘은 딱히 없습니다.
- 조건을 파악한뒤 이제 파이어볼이 이동할수 있는 지도가 연결되어 있다는 것이 중요한 것 같습니다.
- N을 넘어가면 다시 1로 오는 것이죠.
- 방향은 친절하게도 지도모양으로 줘서 8방향탐색 dx,dy를 설정해주시면 되고,
- 저같은 경우 파이어볼들을 저장하는 벡터 하나와 각 단계에서 ground[51][51]을 벡터로 선언해서,
- x,y에 이동한 파이어 볼이 있을경우 push_back으로 각 좌표에 매달아주는 느낌으로 구현하였습니다.
- 그렇게 파이어볼이 모두 이동시킨뒤 ground(맵)을 보면서 파이어볼이 없는 좌표는 continue
- 한개있는 좌표는 그대로 다시 totalfireball에 push, 두개 이상인 것은 문제 조건에 맞춰 재조정한후
- 4개의 파이어볼을 다시 totalfireball에 push 해주었습니다.
- 각 단계에서 vector들 clear()를 해주었구요.
2. 주의사항
- 이게 s(속력)이 최대 1000이 될수도 있습니다.
- 그래서 단순히 0보다 작아지면 N을 더해주거나 N보다 커지면 0으로 만들거나 하려면 이 자체도 반복문 처리를 해주어
- 합니다 그래서 그냥 아래와 같이 처리하였습니다.
- int newx = ((totalfireball[i].x) + dx[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;
int newy = ((totalfireball[i].y) + dy[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;
- 250*N을 더해준 이유는 % 모듈러 연산을 할 때 음수가 나오는 것을 방지하기 위함인데
- N의 최솟값은 4이고 s의 최대값은 1000이므로 250*N은 1000보다 같거나 크면서 N 모듈러 연산에는 영향을 끼치지
- 않는 수로 설정하였습니다(N의배수 이므로)
3. 나의코드
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int N, M, K;
int dx[8] = { -1,-1,0,1,1,1,0,-1 };//8방향탐색
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
struct fireball {
int x,y,m, s, d;
};
vector<fireball> ground[51][51];
vector<fireball> totalfireball;
void inputs() {
cin >> N >> M >> K;
int tx, ty, tm, ts, td;
for(int i=0;i<M;i++){
cin >> tx >> ty>>tm>>ts>>td;
totalfireball.push_back({ tx-1,ty-1,tm,ts,td }); // 난 0~N-1
}
}
void groundclear() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
ground[i][j].clear();
}
}
}
void moveball() {
for (int i = 0; i < totalfireball.size(); i++) {
int newx = ((totalfireball[i].x) + dx[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;
int newy = ((totalfireball[i].y) + dy[totalfireball[i].d] * totalfireball[i].s + 250 * N) % N;
ground[newx][newy].push_back({ newx,newy,totalfireball[i].m,totalfireball[i].s,totalfireball[i].d });
}
}
void makenewball() {
for(int i=0;i<N;i++){
for (int j = 0; j < N; j++) {
if (ground[i][j].empty()) continue; //비어있으면.
else if (ground[i][j].size() == 1) { //파이어볼이 한개
totalfireball.push_back(ground[i][j][0]);
}
else { //두개 이상인 경우
int newm = 0; int news = 0;
for (int k = 0; k < ground[i][j].size(); k++) {
newm += ground[i][j][k].m;
news += ground[i][j][k].s;
}
newm = newm / 5;
if (newm == 0) continue;
news = news / ground[i][j].size();
bool check = false;
for (int k = 0; k < ground[i][j].size(); k++) { //모두 홀수?
if (ground[i][j][k].d % 2 == 0) { check = true; break; }
}
if (check == false) {
totalfireball.push_back({ i,j,newm,news,0 });
totalfireball.push_back({ i,j,newm,news,2 });
totalfireball.push_back({ i,j,newm,news,4 });
totalfireball.push_back({ i,j,newm,news,6 });
continue;
}
check = false;
for (int k = 0; k < ground[i][j].size(); k++) { //모두 짝수?
if (ground[i][j][k].d % 2 == 1) { check = true; break; }
}
if (check == false) {
totalfireball.push_back({ i,j,newm,news,0 });
totalfireball.push_back({ i,j,newm,news,2 });
totalfireball.push_back({ i,j,newm,news,4 });
totalfireball.push_back({ i,j,newm,news,6 });
continue;
}
// 둘다 아닐경우
totalfireball.push_back({ i,j,newm,news,1 });
totalfireball.push_back({ i,j,newm,news,3 });
totalfireball.push_back({ i,j,newm,news,5 });
totalfireball.push_back({ i,j,newm,news,7 });
}
}
}
}
long long getm() {
long long resultm = 0;
for (int i = 0; i < totalfireball.size(); i++) {
resultm += totalfireball[i].m;
}
return resultm;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
inputs();
while (K--) {
groundclear();
moveball();
totalfireball.clear();
makenewball();
}
cout << getm() << "\n";
return 0;
}'알고리즘 문제풀이 > 구현' 카테고리의 다른 글
| 백준 10993 [C++] (0) | 2021.01.16 |
|---|---|
| 백준 20061 [C++] (0) | 2020.12.28 |
| 백준 20055 [C++] (0) | 2020.12.23 |
| 백준 13458 [C++] (0) | 2020.12.15 |
| 백준 15685 [C++] (0) | 2020.12.08 |
