백준(BOJ) 16234 - 인구이동

영역 구하기 응용문제였던 것 같다.

인접한 지역과의 차가 L이상 R 이하인 영역을 벡터에 담고,

담긴 벡터들 값의 평균을 구해 이동된 다음 맵을 만드는 방법을 선택했다.

때문에 맵을 map[50][50][2]형태로 선언하였고,  두맵을 번갈아 가며 사용하게된다.

 방문배열은 매번 초기화 하는 비용을 없애고 싶어서 int형으로 선언하여 이동한 날짜수를 기록해주었다.

사실 인접한 지역을 구하면서 sum값을 구하면 더 효율적인 코드게 되겠지만, 결국 시간복잡도에서는 차이가 없을 것 같아 편하게 답을 구하는쪽으로 코딩했다.

#include <iostream>
#include <vector>
using namespace std;
 
struct _pair{
    int y;
    int x;
};
int N, L, R;
int map[50][50][2];
int visited[50][50];
int k;
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
int abs(int a){
    if(a < 0) a *= -1;
    return a;
}
void check(int y, int x, vector<_pair>& v){
    visited[y][x] = k;
 
    for(int i = 0 ; i < 4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny < 0 || ny >= N || nx < 0 || nx >= N || visited[ny][nx] >= k){
            continue;
        }
        int n = abs(map[y][x][k%2] - map[ny][nx][k%2]);
        if(n >= L && n <= R){
            check(ny, nx, v);
            v.push_back({ny, nx});
        }
    }
}
int main(void){
    scanf("%d %d %d", &N, &L, &R);
    for(int i = 0 ; i < N; i++){
        for(int j = 0 ; j < N; j++){
            scanf("%d", &map[i][j][k]);
            visited[i][j] = -1;
        }
    }
 
    while(true){
        bool result = false;
        vector<_pair> v;
        for(int i = 0 ; i < N; i++){
            for(int j = 0 ; j < N; j++){
                if(visited[i][j] >= k) continue;
                check(i, j, v);
                int n = v.size();
                if(n > 0) result = true;
                int t_sum = map[i][j][k%2], t_cnt = 1 + n;
                for(int l = 0; l < n; l++){
                    int y = v[l].y;
                    int x = v[l].x;
                    t_sum += map[y][x][k%2];
                }
                int value = t_sum / t_cnt;
                for(int l = 0; l < n; l++){
                    int y = v[l].y;
                    int x = v[l].x;
                    map[y][x][(k + 1)%2] = value;
                }
                map[i][j][(k + 1)%2] = value;
                v.clear();
            }
        }
        if(!result) break;
        k++;
    }
 
 
    printf("%d", k);
 
}