[C++] 백준 BOJ 16234 인구 이동

문제링크 : https://noj.am/16234

완탐 + DFS/BFS

// BOJ 16234 인구 이동
#include <iostream>
#include <vector>
 
using namespace std;
 
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
 
struct node {
    int x, y;
};
 
 
int N;  // 크기
int L, R; // 최저, 최대
int sum; // 세포들의 합
int cnt; // 세포 갯수
 
vector<vector<int> > arr; // 세포 배열
vector<vector<bool> > visited; // 방문 체크
vector<node> change; // 바꿀 세포 리스트
 
int abs(int a) {
    return a >= 0 ? a : -a;
}
 
void dfs(node cur) {
    for (int i = 0; i < 4; i++) {
        int nx = cur.x + dx[i];
        int ny = cur.y + dy[i];
 
        if(visited[nx][ny])
            continue;
 
        int diff = abs(arr[cur.x][cur.y] - arr[nx][ny]);
        if(diff >= L && diff <= R){
            visited[nx][ny] = true; // 방문 체크
            change.push_back({nx, ny}); // 변경할 인덱스 추가
            sum += arr[nx][ny]; // 값 누적
            cnt++;  // 세포 카운팅
            dfs({nx, ny});
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("../input.txt", "r", stdin);
 
    cin >> N >> L >> R;
 
    arr = vector<vector<int> >(N + 2, vector<int>(N + 2));
    visited = vector<vector<bool> >(N + 2, vector<bool>(N + 2, true));
 
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            cin >> arr[i][j];
 
    int result = 0;
    while (true) {
        // visited 초기화
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
                visited[i][j] = false;
 
        bool flag = false; // 세포가 변경 되었는지 체크
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (visited[i][j])
                    continue;
                visited[i][j] = true; // 방문 체크
                sum = arr[i][j]; // 값 초기화
                cnt = 1; // 세포 갯수 카운팅
                change.clear();
                change = vector<node>();
                change.push_back({i, j}); // 바꿀 목록에 추가
                dfs({i, j});
 
                // cnt가 1이라는 것은 탐색 못했다는 뜻
                if (cnt == 1)
                    continue;
 
                flag = true;
                int avg = sum / cnt;
                for (auto &c:change)
                    arr[c.x][c.y] = avg;
            }
        }
        // 완탐 돌리는 동안 세포가 변경 안되었으면 탈출
        if (!flag)
            break;
        result++;
    }
 
    cout << result;
 
    return 0;
}