[ 백준 16234 ] 인구 이동 (C++)

[문제보기]

 

[해결과정]

 1. - int형 arr배열, int형 check배열 선언

     - int cnt (나라 합), int sum (나라의 값들을 합한 값), int checkCnt (check배열에 같은 수가 저장되어 있으면 서로 동맹), bool flag (변화가 있는지 없는지, 변화가 없다면 전체 STOP)

 2. n, L, R, arr 입력

 3. while 반복문 실행

   - 방문체크 초기화, checkCnt (=1) 초기화, flag (=true) 초기화

   - arr 배열 전체 순회하면서 방문하지 않았다면 queue에 삽입

   - BFS 실행하며 인원조건이 맞는지 확인, 인원조건이 맞다면 check[i][j] = checkCnt 하고 queue에 삽입, 그리고 cnt++(나라 합) 해주고 sum+=arr[ny][nx] (나라의 값들을 합한 값) 처리

   - BFS를 다 돌고 나오면, num배열의 checkCnt칸에 sum 값 저장

 

 4. arr 배열을 전체 순회하며 arr[i][j] = num[check[i][j] 값으로 변경

 5. 만약 flag == true 라면, 값이 한 번도 바뀐적이 없는 것이므로 반복문 종료

   - 그렇지 않다면 ans ++;

 

[소스코드]

#include<iostream>
#include<vector>
#include<set>
#include<string>
#include<queue>
#include<algorithm>
#include<math.h>
#include<memory.h>
typedef long long ll;
using namespace std;
const int INF = 987987987;
const int MAX = 52;
 
int n, L, R;
int arr[MAX][MAX];
int check[MAX][MAX];
int ans;
 
// 나라 값, 나라 수;
int sum;
int cnt;
 
int checkCnt;
 
bool flag = true;
 
struct coor {
    int y;
    int x;
};
queue <coor> q;
int num[3000];
 
// inside check
bool inside(int y, int x) { return y >= 0 && y < n && x >= 0 && x < n; }
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
void bfs() {
    while (!q.empty()) {
        int y = q.front().y;
        int x = q.front().x;
        q.pop();
 
        int ny, nx;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
 
            if (inside(ny, nx) && check[ny][nx] == 0) {
                // 인원 조건 확인
                int a = abs(arr[y][x] - arr[ny][nx]);
                if (a >= L && a <= R) {
                    check[ny][nx] = checkCnt;
                    sum += arr[ny][nx];
                    cnt += 1;
                    q.push({ ny,nx });
                    flag = false;
                }
            }
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> L >> R;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> arr[i][j];    
    
 
    while (1) {
        // 방문 체크, 체크 카운트, 플래그 초기화
        /*
          방문 체크 : check 배열
          체크 카운트 : 1부터 시작.
          플래그 : while문이 한바퀴 돌았는데, 아무런 변화가 없을 경우 true;
        */
        memset(check, 0, sizeof(check));
        checkCnt = 1;
        flag = true;
 
        // (0,0) 부터 탐색
        // 큐에 넣고 BFS 실행, 방문 체크에 체크 카운트 넣기..
        // 체크 카운트 ++;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (check[i][j] == 0) {
                    check[i][j] = checkCnt;
                    sum = arr[i][j];
                    cnt = 1;
                    q.push({ i,j });
                    bfs();
 
                    num[checkCnt] = sum / cnt;
                    checkCnt++;
                }
            }
        }
 
        // 방문 체크의 수에 따른 계산 값으로 변경
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = num[check[i][j]];    
            }
        }
 
        if (flag == true) break;
        ans++;
 
    }
 
    cout << ans << "\n";
 
    
    return 0;
}

 

[해결 과정 중 실수한 부분]

 처음에 check 배열을 bool로 선언했는데,.. 변경하는 것을 잊어먹고, 값이 이상해서, 디버깅 해보니 계속 동일한 값만 나와서.. 한참 해맸다,.. bool을 int형으로만 변경해주면 금방 끝났을 문제인데, 30분이 더 걸렸다... 시험 때 조심해야겠다.

 

[관련 문제 혹은 비슷한 문제]

 삼성 역량테스트