이게 진정 골드 5 문제인건가.
같은 골드 5보다도 훨씬 어렵잖아!!!
내가 어렵게 푼 걸지도 . . . .
우선 이 문제는 참 재밌는게, 몇개의 연합이 생길지도 모르고, 각 연합마다 인구수를 n등분해서 뿌려주는 것
처음에 풀 때는 연합이 무조건 1개만 생기는 줄 알았는데 .. 그렇게 코드를 짜놓고 생각해보니 아니더라
n개의 연합이 생긴다면? -> vector를 써서 동적으로 연합을 저장하면 되지~
각 땅덩어리 [i][j] 마다 BFS를 돌려버린다.
그러면 국경이 열리는 것들이 한번에 싹 정리가 되고.. 하나의 연합이 만들어짐
그러면 그 연합을 vector에 처 넣고 ~ 인구수 조절을 때리면 된다.
아이디어는 진짜 쉬운데 구현이 너무 어려웠음 ㅜ
//
// Created by 신성준 on 2023/03/26.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <set>
#include <queue>
using namespace std;
int L, R, N;
int Arr[50][50];
vector<set<int>> coops;
int visited[50][50];
void check_coop2(){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++) {
if (visited[i][j]) continue;
visited[i][j] = 1;
set<int> c;
queue<int> q;
q.push(i*N + j);
int idx = i*N + j;
while (!q.empty()) {
idx = q.front();
c.insert(idx);
q.pop();
// cout << idx << ' ' << endl;
int x, y;
x = idx / N;
y = idx % N;
if(x == 0){
int diff = abs(Arr[x][y] - Arr[x+1][y]);
if(diff >= L && diff <= R){
if(!visited[x+1][y]) {
q.push(N*(x+1)+y);
visited[x+1][y] = 1;
}
}
}
else if((x+1) == N){
int diff = abs(Arr[x][y] - Arr[x-1][y]);
if(diff >= L && diff <=R){
if(!visited[x-1][y]) {
q.push(N*(x-1)+y);
visited[x-1][y] = 1;
}
}
}
else{
int diff = abs(Arr[x][y] - Arr[x+1][y]);
if(diff >= L && diff <= R){
if(!visited[x+1][y]) {
q.push(N*(x+1) + y);
visited[x+1][y] = 1;
}
}
diff = abs(Arr[x][y] - Arr[x-1][y]);
if(diff >= L && diff <= R){
if(!visited[x-1][y]) {
q.push(N*(x-1) + y);
visited[x-1][y] = 1;
}
}
}
if(y == 0){
int diff = abs(Arr[x][y] - Arr[x][y+1]);
if(diff >= L && diff <= R){
if(!visited[x][y+1]) {
q.push(N*x + (y+1));
visited[x][y+1] = 1;
}
}
}
else if((y+1) == N){
int diff = abs(Arr[x][y] - Arr[x][y-1]);
if(diff >= L && diff <= R){
if(!visited[x][y-1]) {
q.push(N*x + (y-1));
visited[x][y-1] = 1;
}
}
}
else{
int diff = abs(Arr[x][y] - Arr[x][y+1]);
if(diff >= L && diff <= R){
if(!visited[x][y+1]) {
q.push(N*x + (y+1));
visited[x][y+1] = 1;
}
}
diff = abs(Arr[x][y] - Arr[x][y-1]);
if(diff >= L && diff <= R){
if(!visited[x][y-1]) {
q.push(N*x + (y-1));
visited[x][y-1] = 1;
}
}
}
}
if(c.size() != 1){
coops.push_back(c);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> L >> R;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
cin >> Arr[i][j];
}
}
int cnt = 0;
while(1){
check_coop2();
if(coops.size() == 0) break;
for(int t = 0; t < coops.size(); t++){
int population = 0;
for(auto iter = coops[t].begin(); iter != coops[t].end(); iter++){
int i = *iter / N;
int j = *iter % N;
// cout << i << " " << j << endl;
population += Arr[i][j];
}
// cout << population << endl;
population = population / coops[t].size();
// cout << population << endl;
for(auto iter = coops[t].begin(); iter != coops[t].end(); iter++){
int i = *iter / N;
int j = *iter % N;
Arr[i][j] = population;
}
}
// for(auto i = 0; i < N; i++){
// for(auto j = 0; j < N; j++){
// cout << Arr[i][j] << " ";
// }
// cout << endl;
// }
cnt++;
coops.clear(); //연합 초기화
fill_n(&visited[0][0], 50 * 50, 0); //visited 초기화
}
// for(auto i = 0; i < N; i++){
// for(auto j = 0; j < N; j++){
// cout << Arr[i][j] << " ";
// }
// cout << endl;
// }
cout << cnt;
}
과연 이후에 이 코드를 봤을 때 이해할 수 있을까.