백준 16234번: 인구 이동 (C++)

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

 

단순한 bfs 문제였습니다.

1. 한 좌표에서 bfs로 이차원 배열을 탐색합니다. 탐색 되지 않은 좌표들은 다시 bfs를 돌려줍니다. (다음 노드가 L 이상 R 이하인 부분만 탐색하는 bfs.)

2. 한 좌표에서 bfs를 돌려 탐색 된 부분들은 한 연합입니다. 연합나라들의 수를 분배합니다.(bfs를 돌릴 때 vector에 각 좌표를 저장해두면 쉽게 수를 분배할 수 있습니다.

3. 한 연합 안에서 사람 수들이 모두 같지 않으면 결국 이동을 해야 합니다.

4. 이동할 필요가 없으면 종료해줍니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

#include<iostream> #include<queue> #include<vector>   using namespace std;   int n, L, R; int people[52][52]; bool check[52][52]; int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };   bool bfs(int startx, int starty)  //bfs로 탐색하고 연합들 인구 수 분배 {     queue<pair<int, int>> q;     vector<pair<int, int>> v;     q.push(make_pair(startx, starty));     check[startx][starty] = true;       int sum = 0;     int count = 0;     while (!q.empty())     {         int x = q.front().first;         int y = q.front().second;         q.pop();           sum += people[x][y];          //탐색하면서 사람들 수 더하기         count++;         v.push_back(make_pair(x,y));           for (int d = 0; d < 4; d++)    //방향 선택         {             int nextx = x + dir[d][0];             int nexty = y + dir[d][1];             if (nextx < 0 || nexty < 0 || nextx >= n || nexty >= n)continue;             if (check[nextx][nexty])continue;               int gap = abs(people[x][y] - people[nextx][nexty]);             if (gap >= L && gap <= R)               {                 check[nextx][nexty] = true;                 q.push(make_pair(nextx, nexty));             }         }     }       int standard = people[v[0].first][v[0].second];     bool moving = false;;     for (int i = 0; i < v.size(); i++)           //인구 수 분배     {         int x = v[i].first;         int y = v[i].second;         if (standard != people[x][y])moving = true;  //값이 모두 같지 않으면 이동해야함         people[x][y] = sum / count;     }     return moving; }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);       cin >> n >> L >> R;       for (int i = 0; i < n; i++)     {         for (int j = 0; j < n; j++)         {             cin >> people[i][j];         }     }       int count = 0;     while (1)     {         bool moving = false;         fill(&check[0][0], &check[49][50], 0);         for (int i = 0; i < n; i++)         {             for (int j = 0; j < n; j++)             {                 if (check[i][j])continue;                 if(bfs(i, j))moving=true; //한번이라도 이동하면 moving이 true로 됨             }         }         if (moving == false)break;  //이동한적이없으면 탈출         count++;     }       cout << count << "\n";       return 0; }

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.