• 문제 : https://www.acmicpc.net/problem/16234

---

1. 문제 접근

인구이동의 조건을 만족시키면서 DFS로 탐색하기만 하면 되는 문제

• 인구이동이 더이상 일어나지 않을 때까지 아래의 상황 반복
  • 모든 좌표값에 대해 DFS탐색
  • 국경선을 공유하는 두 나라의 인구 차이가 L명 이상 R명 이하일 때, 국경선 개방
  • 국경선을 개방한 모든 칸들(연합)을 찾아야 함 => connected component 찾기
  • 해당 연합의 인구를 모두 더하고, 국가의 수만큼 나눠서 분배(소수점 이하 절삭)

---

2. 시행착오

• 없음

---

3. 코드 및 풀이

3.1 풀이

• dfs()를 통해서 조건을 만족하는 '연합'을 찾아, 해당 연합을 이루는 좌표값들을 벡터 v에 넣어 connected component를 구하는 함수
• movePeople() : v에 들어간 국가들 인구이동하는 함수
• isMove 만약에 벡터 v의 원소의 개수가 2 이상이라면(하나일때는 자기 자신일 수도 있으니, 인구이동 X), true로 바꿔줌
  • 그렇다면, 모든 좌표값에 대한 탐색에도 불구하고 인구이동이 일어나지 않다면 isMove는 false일테니, while문 종료하고 정답 반환
  • 인구이동이 일어나면 ret 1씩 추가

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

const int dy[4] = {0, 1, 0, -1};
const int dx[4] = {1, 0, -1, 0};

int N, L, R, ret;
int ny, nx;
int adj[54][54];
int visited[54][54];
vector<pair<int, int>> v;

bool isValid(int y, int x){
    return (0 <= y && y < N && 0 <= x && x < N);
}

// dfs 재귀적으로 하면서, 국경 열어야 하는 좌표 담음
void dfs(int y, int x){
    visited[y][x] = 1;
    v.push_back({y, x});
    for(int i = 0; i < 4; i++){
        ny = y + dy[i];
        nx = x + dx[i];
        int cha = abs(adj[ny][nx] - adj[y][x]);
        
        if(isValid(ny, nx) &&
            !visited[ny][nx] &&
            L <= cha && cha <= R) {
            dfs(ny, nx);
        }
    }
}

// 인구이동
void movePeople(){
    int sum_p = 0;
    int cnt = 0;
    
    for(auto it : v) {
        sum_p += adj[it.first][it.second]; cnt++;
    }
    int new_p = sum_p / cnt;
    
    for(auto it : v) {
        adj[it.first][it.second] = new_p;
    }
    
}

int main(){
    // input
    cin >> N >> L >> R;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> adj[i][j];
        }
    }
    
    // 완전탐색
    while(true){
        bool isMove = false;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if (!visited[i][j]) {
                    dfs(i, j);
                    // 인구이동 가능성이 있으면, 일수 더하기
                    if (v.size() >= 2) {
                        isMove = true;
                        movePeople(); 
                    }
                    // 다음 v를 위해 초기화
                    v.clear();
                }
            }
        }
        // 한번도 이동하지 않았다면
        if (!isMove) break;
        // 새로운 도전을 위해 초기화
        else {
            ret++;
            fill(&visited[0][0], &visited[0][0] + 54 * 54, 0);
        }
    }
    cout << ret;

}

---

Reference