[알고리즘] 백준 16234

백준 16234번 인구 이동

해결 과정 요약

dfs를 이용해 연합국가를 모두 구해주고
그들의 총 인구수, 총 국가수를 저장해둔다.
그리고 dfs가 끝난 뒤 연합국가의 인구수를 최신화시켜준다.
연합국가가 만들어질 수 없을 때까지 반복하고 총 반복횟수를 출력한다.

풀이

#include <bits/stdc++.h>
using namespace std;

int N,L,R,sum,cnt;
int m[50][50];
int visited[50][50];
int localVisit[50][50];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

void reset(){
    sum = 0;
    cnt = 0;
    fill(&localVisit[0][0], &localVisit[0][0] + 2500, 0);
}

void update(){
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(localVisit[i][j])
                m[i][j] = sum/cnt;
        }
    }
}

int dfs(int y, int x, int toggle){
    visited[y][x] = 1;
    localVisit[y][x] = 1;
    sum += m[y][x];
    cnt++;
    for(int i=0; i<4; i++){
        int ny = y + dy[i];
        int nx = x + dx[i];
        if(ny<0 || nx<0 || ny>=N || nx>=N || visited[ny][nx]) continue;
        int sub = abs(m[ny][nx] - m[y][x]);
        if(sub >= L && sub <= R){
            toggle = dfs(ny, nx, 1);
        }
    }
    return toggle;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> L >> R;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> m[i][j];
        }
    }
    int tmp = 0;
    int ret = 0;
    while(true){
        fill(&visited[0][0], &visited[0][0] + 2500, 0); tmp = 0;
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                if(!visited[i][j]){
                    reset();
                    tmp += dfs(i, j, 0);
                    if(cnt > 1) update();
                }
            }
        }
        if(tmp) ret++;
        else break;
    }
    cout << ret;
    
    return 0;
}

코멘트

알고리즘은 어렵지 않은데 연합국가의 인구수 최신화, 연합국가가 만들어질 수 있는지 없는지 확인하기 등등.. 구현할 것들이 많아서 쉽지 않았던 문제다.

localVisit배열을 써서 dfs를 호출할 때마다 전체 배열을 초기화하며, update를 할때도 전체 배열을 탐색해야해서 시간이 오래걸렸다. 물론 이렇게 해도 시간초과가 안날걸알고 빠르게 구현하기위해 이렇게 했다.
시간을 줄이고자 한다면 2차원배열 대신에 vector<piar<int,int>> 를 사용하면 된다.