[백준 16234]인구 이동

문제 https://www.acmicpc.net/problem/16234

1)문제 분류

-시뮬레이션

-DFS

-BFS

2)문제 해결

- 맵을 탐색시, 연합할 수 있는 나라들끼리 묶는다.

- 그리고 연합한 나라들끼리 인구이동을 시킨다.

- 이때 , chk배열을 둬서 인구이동이 이미 끝난 나라는 건들지 않도록 체크한다.

- 종료 조건은 맵을 다 탐색했음에도, 인구이동이 한번이라도, 일어나지 않았다면 종료한다.

#include<iostream>

#include<queue>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

int N, L, R;

int flag;

int ans = 0;

int chk[52][52];

int map[52][52];

int xrr[4] = { 0,0,1,-1 };

int yrr[4] = { 1,-1,0,0 };

vector<pair<int, int>>temp;

void make_filed(int x, int y)

{

int hap = map[x][y];

int cnt = 1;

queue<pair<int, int>>pq;

pq.push({ x,y });

temp.push_back({ x,y });

chk[x][y] = true;

while (!pq.empty())

{

int outx = pq.front().first;

int outy = pq.front().second;

pq.pop();

for (int i = 0; i < 4; i++)

{

int nx = outx + xrr[i];

int ny = outy + yrr[i];

if (nx<0 || ny<0 || nx>N - 1 || ny>N - 1 || chk[nx][ny] == true)continue;

int De = abs(map[outx][outy] - map[nx][ny]);

if (De >= L&&De <= R)

{

flag = 1;//인구이동있음

chk[nx][ny] = true;

cnt++;

hap += map[nx][ny];

pq.push({ nx,ny });

temp.push_back({ nx,ny });

}

}

}

int data = hap / cnt;

for (int i = 0; i < temp.size(); i++)

{

map[temp[i].first][temp[i].second] = data;

}

temp.clear();

}

int main()

{

cin >> N >> L >> R;

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

{

scanf("%d",&map[i][j]);

}

}

while (1)

{

flag = 0;

memset(chk, false, sizeof(chk));

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

{

if (chk[i][j] == false)

{

make_filed(i, j);

}

}

}

if (flag == 0)

{

printf("%d\n", ans);

return 0;

}

ans++;

}

}