백준 20056 마법사 상어와 파이어볼
https://www.acmicpc.net/problem/20056
20056번: 마법사 상어와 파이어볼
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치
www.acmicpc.net
- 시뮬레이션 + 구현 문제이다. 시간복잡도는 k번 이동 * 각 이동마다 m개의 파이어볼이 이동하므로 O(km)이다.
- 필자는 모든 정보를 vector 하나로 해결했다. vector에 들어가는 요소들은 순서대로 질량, 속력, 방향, 이동 여부이다.
- 가장 먼저, 파이어볼의 정보를 받아 push_back한다. 이 후, 총 k번의 이동을 진행한다.
1. 파이어볼이 자신의 방향과 속력을 활용하여 다음 칸으로 이동한다. 이 때, 속력만큼 for문을 통해 한 칸씩 이동을 하는데, 1번 행(열)0과 n번 행(열)이 연결되어 있으므로, 이를 잘 활용하여 이동 중 1과 n 사이를 벗어나는 경우를 잘 처리 해 준다. 이 후, 파이어볼이 이동을 마치면 기존 좌표의 파이어볼을 erase 해 주고, 새로운 좌표에 해당 파이어볼을 push_back 한다. 이렇게 이동해야 하는 파이어볼들이 모두 이동을 했다면 while문을 빠져나오게 된다. 이 과정에서, 해당 좌표에서 존재하던 파이어볼들이 모두 이동해야 했던 상황이라면(즉, second.second가 false) while 조건 체크에서 오류가 날 수 있으므로 해당 좌표가 비었을 때 break를 해 주도록 조건을 추가 해 준다.
2. 다음으로, 모든 파이어볼들의 이동여부를 false로 초기화 해 준다.(다음 이동을 위해)
3. 이제 하나의 area에 2개 이상의 파이어볼이 존재하는지를 체크 한다. 2개 이상이 존재한다면, 주어진 조건대로 질량과 속력, 방향을 계산해서 새로 해당 area에 push를 하면 된다.
- 1시간 10분정도가 걸린 문제이다. 이유는 변수를 잘못 입력받고, 2번 과정을 빼먹어서.. ㅜㅜ 그래도 구현 능력이 많이 늘었다는 것에 의의를 둔다.
#include <iostream>
#include <vector>
int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 1,1,1,0,-1,-1,-1 };
int n, m, k;
using namespace std;
vector<pair<pair<int, int>, pair<int, bool>>> v[51][51];
void debugging() {
for (int i = 1; i <= n; i++) { // 자신의 칸으로 이동
for (int j = 1; j <= n; j++) {
cout << v[i][j].size() << ' ';
}
cout << '\n';
}
cout << '\n';
}
int main() {
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int r, c, m, d, s;
cin >> r >> c >> m >> s >> d;
v[r][c].push_back({{ m,s }, { d,false }});
}
while (k--) {
for (int i = 1; i <= n; i++) { // 자신의 칸으로 이동
for (int j = 1; j <= n; j++) {
if (v[i][j].empty()) continue;
while (v[i][j][0].second.second == false) { // 아직 이동을 안 한 파이어볼이라면
int s = v[i][j][0].first.second; int m = v[i][j][0].first.first; int d = v[i][j][0].second.first;
int nx = i; int ny = j;
for (int k = 0; k < s; k++) {
nx += dx[d]; ny += dy[d];
if (nx == n + 1) nx = 1; if (ny == n + 1) ny = 1;
if (nx == 0) nx = n; if (ny == 0) ny = n;
}
v[i][j].erase(v[i][j].begin());
v[nx][ny].push_back({ { m, s },{ d,true } });
if (v[i][j].empty()) break;
}
}
}
for (int i = 1; i <= n; i++) { // 이동여부 초기화
for (int j = 1; j <= n; j++) {
for (int k = 0; k < v[i][j].size(); k++) v[i][j][k].second.second = false;
}
}
for (int i = 1; i <= n; i++) { // 2개 이상의 파이어볼이 존재하는 경우 처리
for (int j = 1; j <= n; j++) {
if (v[i][j].size() < 2) continue;
int sum_m, sum_s; sum_m = sum_s = 0;
bool is_odd = true; bool all_same = true;
if ((v[i][j][0].second.first) % 2 == 0) is_odd = false;
for (int k = 0; k < v[i][j].size(); k++) {
sum_m += v[i][j][k].first.first; sum_s += v[i][j][k].first.second;
if (is_odd && (v[i][j][k].second.first) % 2 != 1) all_same = false;
if (!is_odd && (v[i][j][k].second.first) % 2 != 0) all_same = false;
}
int new_m = sum_m / 5; int new_s = sum_s / v[i][j].size();
int start_d = 1;
if (all_same) start_d--;
v[i][j].clear();
if (new_m != 0) {
for (int k = 0; k < 4; k++) {
v[i][j].push_back({ { new_m, new_s },{ (k * 2) + start_d, false } });
}
}
}
}
}
int answer = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 0; k < v[i][j].size(); k++) {
answer += v[i][j][k].first.first;
}
}
}
cout << answer;
return 0;
}