Algorithm) 백준 16234 인구이동 c++

bfs 문제입니다만 약간 신경써줘야 하는 bfs입니다.

 

대략적으로 풀이 방식을 설명하자면

for문으로 모든 국가를 돌면서 국경선을 열 수 있는 나라와 방향을 체크하고 bfs를 돌아서 연결된 나라들의 인구수를 나누는 방식입니다. 

 

 

디버깅하면서 잘못된 로직을 하나하나 고치다보니 코드가 좀 지저분해져서 코드에 주석으로 설명 써놓았습니다!

#include <iostream>
#include <queue>
#include <cmath>
#include <vector>
using namespace std;

int dy[4] = {-1,0 , 1, 0};
int dx[4] = {0, 1, 0, -1};
int line[51][51][4];
int arr[51][51];
int visited[51][51];
int n,l,r;
int cnt = 0;


void input() { //입력
    cin>>n>>l>>r;
    for(int i=1; i<=n; i++) {
        for(int j=1; j <=n; j++) {
            cin>>arr[i][j];
        }
    }
}

void clear() { //초기화
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            visited[i][j] = 0;
            for(int d=0; d<4; d++) {
                line[i][j][d]= 0;
            }
        }
    }
}

void connect() { //국경 개방
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            for(int d=0; d<4; d++) {
                if(i+dy[d] >=1 && i+dy[d] <=n && j+dx[d] >=1 && j+dx[d] <=n) {
                    if(abs(arr[i][j]-arr[i+dy[d]][j+dx[d]]) >= l && abs(arr[i][j]-arr[i+dy[d]][j+dx[d]])<=r ) {
                        line[i][j][d]=1;
                    }
                }
            }
        }
    }
}

void divide(int quotient, int share) { //인구수 나누기
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(visited[i][j]==share) {
                arr[i][j] = quotient;
            }
        }
    }
}
void move() {
    while(1) {
        clear();
        connect();
        bool flag = false; //인구이동이 일어났는지
        int share = 1;
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {

                bool isMoved = false; //arr[i][j]에서 시작해서 인구 이동이 일어났는지
                if(visited[i][j]!= 0) { continue; } //이미 bfs에 들어갔던 나라는 제외
                int country = 1; //연결된 국가의 수 
                int people = arr[i][j]; //연결된 국가들의 총 인구수
                queue<pair<int,int>> q;
                for(int d=0; d<4; d++) { //4방 체크
                    if(line[i][j][d]==1) {
                        flag = true;
                        isMoved = true;
                        q.push({i+dy[d], j+dx[d]});
                    }
                }
                if(isMoved) {
                    visited[i][j] = share; //share는 1 2 3 4 이렇게 연결된 덩어리를 뜻함 1번끼리 연결,  2번끼리 연결 ...
                }

                while(!q.empty()) { //bfs
                    auto cur = q.front(); q.pop();
                    country++;
                    people+= arr[cur.first][cur.second];
                    visited[cur.first][cur.second] = share;
                    for(int d=0; d<4; d++) {
                        if(cur.first+dy[d]<1 || cur.first + dy[d]>n || cur.second + dx[d] <1 || cur.second + dx[d] > n) continue;
                        if(visited[cur.first+dy[d]][cur.second+dx[d]]!=0) continue;
                        if(line[cur.first][cur.second][d]==1) {
                            q.push({cur.first+dy[d], cur.second+dx[d]});
                            visited[cur.first+dy[d]][cur.second+dx[d]] = share;
                        }
                    }
                }

                if(country>=2) { //연결 되었다면 
                    int sharedPeople = people/country;
                    divide(sharedPeople, share);
                    share++;
                }
            }
        }
        if(!flag) break;
        cnt++;
    }
}

void solve() {
    input();
    move();
    cout<<cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
}