반응형
https://www.acmicpc.net/problem/23290
23290번: 마법사 상어와 복제
첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향
www.acmicpc.net
물고기를 한마리 한마리 처리하는 게 아니라
같은 좌표에서 같은 방향을 가리키는 물고기가 몇마리 있는 지 세어주는 식으로 구현하면
메모리를 상당히 아낄 수 있다.
처음에 문제를 읽을 때는 물고기 한마리 한마리 벡터에 넣어주면서 풀었는데
어차피 중요한건 물고기의 수이므로 같은 좌표 같은 방향 물고기를 한번에 이동시켜주면
메모리와 함께 시간도 절약할 수 있다.
그리고 상어의 이동은 3칸이동하므로 간단히 반복문으로 구현하고
이동 내에서 중복된 칸이 있는지 체크하기 위해 set을 이용하여 여러번 방문한 칸이어도
물고기들을 한번만 없애주도록 만들었다.
#include <bits/stdc++.h>
using namespace std;
int skx, sky, S, smell[5][5];
int fishes[5][5][9], fishCopy[5][5][9];
void Input() {
int M;
cin >> M >> S;
for (int i = 1; i <= M; i++) {
int fx, fy, d;
cin >> fx >> fy >> d;
fishes[fx][fy][d]++;
}
cin >> skx >> sky;
}
void copyMagic() {
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
for (int k = 1; k <= 8; k++) {
fishCopy[i][j][k] = fishes[i][j][k];
}
}
}
}
void fishesMove() {
int dx[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
int dy[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};
int tmp[5][5][9];
memset(tmp, 0, sizeof(tmp));
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
for (int k = 1; k <= 8; k++) {
int dir = k;
bool flag = false;
for (int t = 1; t <= 8; t++) {
int nx = i + dx[dir];
int ny = j + dy[dir];
if (nx <= 0 || nx > 4 || ny <= 0 || ny > 4 || smell[nx][ny] || (nx == skx && ny == sky)) {
//반시계회전
dir = dir - 1;
if (dir == 0) dir = 8;
} else {
flag = true;
tmp[nx][ny][dir] += fishes[i][j][k];
break;
}
}
//이동할 수 없는 경우
if (!flag) {
tmp[i][j][k] += fishes[i][j][k];
}
}
}
}
swap(tmp, fishes);
}
void sharkMove() {
int dx[5] = {0, -1, 0, 1, 0};
int dy[5] = {0, 0, -1, 0, 1};
int maxSum = -1;
int nskx = -1, nsky = -1;
vector<pair<int, int> > toSmell;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
for (int k = 1; k <= 4; k++) {
int firstX = skx + dx[i], firstY = sky + dy[i];
int secX = firstX + dx[j], secY = firstY + dy[j];
int thirdX = secX + dx[k], thirdY = secY + dy[k];
if (firstX <= 0 || firstX > 4 || firstY <= 0 || firstY > 4) continue;
if (secX <= 0 || secX > 4 || secY <= 0 || secY > 4) continue;
if (thirdX <= 0 || thirdX > 4 || thirdY <= 0 || thirdY > 4) continue;
int sum = 0;
set<pair<int, int> > Set;
Set.insert({firstX, firstY});
Set.insert({secX, secY});
Set.insert({thirdX, thirdY});
for (auto a: Set) {
for(int b=1; b<=8; b++){
sum += fishes[a.first][a.second][b];
}
}
if (sum > maxSum) {
maxSum = sum;
toSmell.clear();
nskx = thirdX;
nsky = thirdY;
for (auto a: Set) {
toSmell.push_back({a.first, a.second});
}
}
}
}
}
for (auto a: toSmell) {
int sum = 0;
for(int b=1; b<=8; b++){
sum += fishes[a.first][a.second][b];
}
if (sum) {
smell[a.first][a.second] = 3;
memset(fishes[a.first][a.second], 0 ,sizeof(fishes[a.first][a.second]));
}
}
skx = nskx;
sky = nsky;
}
void smellErase() {
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if (smell[i][j]) {
smell[i][j]--;
}
}
}
}
void appendCopy() {
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
for(int k=1; k<=8 ;k++){
fishes[i][j][k] += fishCopy[i][j][k];
}
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
Input();
for (int i = 0; i < S; i++) {
copyMagic();
fishesMove();
sharkMove();
smellErase();
appendCopy();
}
int ans = 0;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
for(int k=1; k<=8 ;k++){
ans += fishes[i][j][k];
}
}
}
cout << ans << '\n';
return 0;
}반응형
'Algorithm > problem' 카테고리의 다른 글
| 백준 15486번 : 퇴사 2 - DP (0) | 2022.09.02 |
|---|---|
| 백준 23291번 : 어항 정리 - 시뮬레이션 C++ (0) | 2022.08.29 |
| 백준 23289번 : 온풍기 안녕! - 시뮬레이션 C++ (0) | 2022.08.27 |
| 백준 23288번 : 주사위 굴리기 2, 시뮬레이션 C++ (0) | 2022.08.26 |
| 백준 21611번: 마법사 상어와 블리자드 - C++ (0) | 2022.08.25 |