[백준 C++] 16234 인구 이동 - 너비우선탐색

16234번: 인구 이동

---

 

문제풀이

 

너비 우선 탐색을 이용해서 푸는 시뮬레이션 유형의 문제입니다.

미방문 노드에서 BFS를 시작해서 연합 영역을 큐에 저장해주고

연합의 크기가 2이상일 때 인구 이동을 시켜주었습니다.

인구 이동이 더이상 이뤄지지 않을 때까지 해당 로직을 반복해서 시뮬레이션하도록 구현했습니다.

---

코드

cpp

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

typedef pair<int, int> p;

const int DX[4] = { -1, 0, 1, 0 };
const int DY[4] = { 0, -1, 0, 1 };

int N, gL, gR;
int Num[50][50];

int Cnt, Sum;
bool Visited[50][50];
queue<p> NQ;

void BFS(int SR, int SC)
{
‌queue<p> SQ;
‌Visited[SR][SC] = true;
‌SQ.emplace(SR, SC);
‌NQ.emplace(SR, SC);
‌while (!SQ.empty())
‌{
‌‌int R = SQ.front().first;
‌‌int C = SQ.front().second;
‌‌SQ.pop();

‌‌++Cnt;
‌‌Sum += Num[R][C];
‌‌for (int i = 0; i < 4; ++i)
‌‌{
‌‌‌int NR = R + DY[i];
‌‌‌int NC = C + DX[i];
‌‌‌if (NR < 0 || NR > N - 1 || NC < 0 || NC > N - 1
‌‌‌‌|| Visited[NR][NC]
‌‌‌‌|| abs(Num[R][C] - Num[NR][NC]) < gL
‌‌‌‌|| abs(Num[R][C] - Num[NR][NC]) > gR)
‌‌‌{
‌‌‌‌continue;
‌‌‌}

‌‌‌Visited[NR][NC] = true;
‌‌‌SQ.emplace(NR, NC);
‌‌‌NQ.emplace(NR, NC);
‌‌}
‌}
}

bool Move()
{
‌bool bMove = false;

‌memset(Visited, false, sizeof(Visited));
‌for (int i = 0; i < N; ++i)
‌{
‌‌for (int j = 0; j < N; ++j)
‌‌{
‌‌‌if (Visited[i][j])
‌‌‌{
‌‌‌‌continue;
‌‌‌}

‌‌‌Cnt = 0;
‌‌‌Sum = 0;

‌‌‌BFS(i, j);
‌‌‌if (Cnt == 1)
‌‌‌{
‌‌‌‌NQ.pop();
‌‌‌‌continue;
‌‌‌}

‌‌‌while (!NQ.empty())
‌‌‌{
‌‌‌‌int R = NQ.front().first;
‌‌‌‌int C = NQ.front().second;
‌‌‌‌NQ.pop();

‌‌‌‌Num[R][C] = Sum / Cnt;
‌‌‌‌bMove = true;
‌‌‌}
‌‌}
‌}

‌return bMove;
}

int main()
{
‌ios::sync_with_stdio(false);
‌cin.tie(nullptr); cout.tie(nullptr);

‌cin >> N >> gL >> gR;
‌for (int i = 0; i < N; ++i)
‌{
‌‌for (int j = 0; j < N; ++j)
‌‌{
‌‌‌cin >> Num[i][j];
‌‌}
‌}

‌int Day = 0;
‌while (Move())
‌{
‌‌++Day;
‌}

‌cout << Day;
}