백준 16235번 인구 이동 문제 풀이

문제 설명

문제를 보고 든 생각

• 나라가 각각 따로 따로 병합이 되는 경우도 있겠다.
• 위의 경우에는 따로 병합될 때 섞이지 않도록 조심해야겠다.
• 소수점은 버리기 때문에 int 자료형을 사용해야겠다.
• 병합해야 하는 나라의 목록을 vector에 저장해보자.
• 각 셀마다 dfs로 완전 탐색을 해서 합쳐야 하는 국가의 목록을 vector에 저장하자.
• 기능별로 함수를 잘 나눠보자!

풀이 간단 설명

1. 이동 후의 인구 수를 저장하는 배열 nation
2. 이동 중간 중간 합쳐진 나라마다 인구 수를 저장하는 배열 unionedMap
3. 합쳐야 하는 나라의 정보를 반환하는 함수 unionNationVector
4. unionedMap에 인구 이동을 임시 저장하는 함수 unionAtUnionedMap (nation 배열에 바로 저장하면 인구 이동과 경계선을 허무는 과정이 동시에 진행되기 때문에 임시 저장한다.)
5. 방문 체크를 해서 dfs 횟수를 줄여보았다.
6. nation 과 unionMap의 싱크를 맞춰주는 함수 syncMap
7. initVisit => initUinonedMap => 각 셀마다 (unionNationVector => unionAtUnionedMap) => syncMap
8. 더 이상 인구 이동을 할 수 없으면 반복문을 탈출한다.

코드

#include <iostream>
#include <vector>

#define MAX_N 50

using namespace std;

struct pos{
  int r, c;
};


int N, L, R;
int nation[MAX_N+1][MAX_N+1];
int unionedMap[MAX_N+1][MAX_N+1];
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

void getInput(){
  cin >> N >> L >> R;
  for(int i=1; i<=N; ++i){
    for(int j=1; j<=N; ++j){
      cin >> nation[i][j];
    }
  }
}

bool boundCheck(int r, int c){
  return r < 1 || c < 1 || r > N || c > N;
}

vector<pos> unionNationVector(int _r, int _c, bool visited[][MAX_N+1]){
  vector<pos> v;
  if(boundCheck(_r, _c)){
    return v;
  }
  if(visited[_r][_c]){
    return v;
  }
  visited[_r][_c] = true;
  
  const int currPeople = nation[_r][_c];

  for(int i=0; i<4; ++i){
    int nr = _r + dir[i][0];
    int nc = _c + dir[i][1];
    if(boundCheck(nr, nc)){
      // out of bound
      continue;
    }
    if(visited[nr][nc]){
      // visited
      continue;
    }
    const int nextPeople = nation[nr][nc];
    const int diffPoeple = abs(currPeople - nextPeople);
    if(diffPoeple < L || R < diffPoeple){
      // not in range
      continue;
    }
    v.push_back({nr, nc});
    vector<pos> dfsV = unionNationVector(nr, nc, visited);
    v.insert(v.end(), dfsV.begin(), dfsV.end());
  }

  return v;
}

void initVisit(bool visit[][MAX_N+1]){
  for(int i=1; i<=N; ++i){
    for(int j=1; j<=N; ++j){
      visit[i][j] = false;
    }
  }
}

void initUnionedMap(){
  for(int r=1; r<=N; ++r){
    for(int c=1; c<=N; ++c){
      unionedMap[r][c] = nation[r][c];
    }
  }
}

int syncMap(){
  int diffCnt = 0;
  for(int r=1; r<=N; ++r){
    for(int c=1; c<=N; ++c){
      if(nation[r][c] == unionedMap[r][c]){
        continue;
      }
      nation[r][c] = unionedMap[r][c];
      ++diffCnt;
    }
  }

  return diffCnt;
}

void unionAtUnionedMap(vector<pos> v){
  int cellCnt = v.size();
  int peopleSum = 0;
  for(auto &it : v){
    peopleSum += nation[it.r][it.c];
  }
  int peopleCell = peopleSum/cellCnt;

  for(auto &it : v){
    unionedMap[it.r][it.c] = peopleCell;
  }
}

void solve(){
  getInput();
  int cnt = 0;
  while(true){
    // start
    bool visit[MAX_N+1][MAX_N+1];
    initVisit(visit);
    initUnionedMap();
    
    for(int r=1; r<=N; ++r){
      for(int c=1; c<=N; ++c){
        vector<pos> v = unionNationVector(r, c, visit);
        if(v.empty()){
          // no union
          continue;
        }
        v.push_back({r, c}); // push back current territory
        unionAtUnionedMap(v);
      }
    }
    int diffCnt = syncMap();
    if(diffCnt == 0){
      cout << cnt;
      return;
    }
    //end
    ++cnt;
  }

}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();

  return 0;
}