39. [백준 21610번 / C++] 마법사 상어와 비바라기
https://www.acmicpc.net/problem/21610
이번에도 상어가 새로운 마법을 익혔습니다! 그만 공부해...
매일매일 풀던 코테가 요즘 며칠에 한 문제씩 푸니까 뭔가 굉장히 어색하네요. 면접이 급하니까 어쩔 수 없다지만 뭔가 묘한 느낌이랄까..??
어찌되었든 문제를 보면
이 문제는 굉장히 간단한 점이 문제의 조건만 그대로 따라가기만 하면 반례없이 그냥 통과되는 코드였습니다!
다만, 문제 조건 5번에서 '3번에서 구름이 사라진 칸은 구름이 생겨선 안된다' 이 부분을 구현하는게 아주 약간은? 까다로운 문제였던 것 같습니다. 바로 코드를 보면
#include<bits/stdc++.h>
using namespace std;
const int dy[] = {0, -1, -1, -1, 0, 1, 1, 1};
const int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int n, m, a[54][54], b[54][54], d, s, ret; // a는 물 바구니, b는 구름
void bibaragi(){ // 비바라기 시전! 중에서 맨 처음 구름 만들기.
b[n - 1][0] = 1;
b[n - 1][1] = 1;
b[n - 2][0] = 1;
b[n - 2][1] = 1;
}
void move(int d, int s){
vector<pair<int, int>> v;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(b[i][j]){
int ny = i + dy[d] * s;
int nx = j + dx[d] * s;
ny = (ny + n) % n;
nx = (nx + n) % n;
b[i][j] = 0;
v.push_back({ny, nx});
}
}
}
for(auto i : v){
b[i.first][i.second] = 1;
}
}
void rain(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(b[i][j]) a[i][j]++;
}
}
}
void waterBug(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(b[i][j]){
for(int k = 1; k < 8; k += 2){
int ny = i + dy[k];
int nx = j + dx[k];
if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if(a[ny][nx] > 0) a[i][j]++;
}
}
}
}
}
void makeCloud(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(b[i][j] == 1) b[i][j] = 0;
else if(b[i][j] == 0 && a[i][j] >= 2){
b[i][j]++;
a[i][j] -= 2;
}
}
}
}
//void printCloud(){
// cout << "---------cloud-------------\n";
// for(int i = 0; i < n; i++){
// for(int j = 0; j < n; j++){
// cout << b[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "---------water-------------\n";
// for(int i = 0; i < n; i++){
// for(int j = 0; j < n; j++){
// cout << a[i][j] << " ";
// }
// cout << "\n";
// }
//}
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> a[i][j];
}
}
bibaragi();
for(int i = 0; i < m; i++){
cin >> d >> s;
d--; s %= n;
move(d, s);
rain();
//erase cloud
waterBug();
makeCloud();
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
ret += a[i][j];
}
}
cout << ret << "\n";
}
a배열은 물을 담는 바구니(물의 양), b배열은 구름이 있는 장소를 표기합니다.
먼저, 조건 1을 구현하기 위해서 move함수를 사용하기 전에 s를 모듈러 연산을 이용해 s %= n을 해주어야합니다. 왜냐하면 배열의 바깥으로 나가는게 아니라 'n번행과 1번행이 이어져있기 때문'이죠. 열에서도 마찬가지입니다.
그 이후 move를 이용해서 구름을 옮겨줍니다.
다음 2번 조건으로 rain()을 통해서 그냥 구름이 있는 장소에 비를 내려 a[ ][ ]++해줍니다.
3번조건은 구름을 지우는 것인데... 전 일단 지우지 않았습니다. 주석처리된 erase cloud가 보이시죠?
4번 조건의 물복사버그가 waterBug()를 통해서 이루어집니다. 이것도 간단하죠? 배열이 이어져있는 것이 아니라고 생각하고 바구니의 개수를 세는 것이기 때문에 dfs나 bfs에 숙달되신 분이라면 금방 확인하실 수 있을거예요.
한가지 재밌는 점은 4번 조건의 '물이 증가한 곳'은 3번에서 지우지 않은 구름이 있는 위치와 동일하다는 것입니다!
(물이 증가 = 비가 내림 = 구름있음)
이제 가장 중요한 5번 조건인데요. makeCloud()에서 3번 조건에서 지우지 않은 구름을 지우고, 구름을 만들어줍니다. 3번 조건에서 구름을 지우지 않았던 이유가 바로 이것이예요!
'3번 조건에서 사라진 구름은 다시 생기면 안된다' 라는 것을 구현하기 위해서 그냥 단순하게 b[ ][ ]가 이미 1이라면 아 구름이 있었던 상태였구나! 하고 지우고,
b[ ][ ] = 0이고 a[ ][ ] >= 2라면 구름이 생기게 처리하면 3번 조건에 따라 구름도 없어지고 5번 조건에 따라 3번에서 없어진 구름은 다시 생기지 않게 구름을 만들 수 있습니다.
끝!
