16234번-인구이동

문제

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

---

접근방법

1) 접근 사고

구현량이 많은 구현 문제였습니다. 갱신 이후에 갱신을 할 것인지 말 것인지 구분하는 부분을 작성하는 부분이 핵심 구현입니다. 처음에 visited로 갱신 부분과 중복 부분을 같이 사용하였으나 값을 갱신할 때 값이 중복되는 부분이 생기는것을 알았습니다.(국가와 국가가 i, j번 타이밍에 연합되는 것을 i, j + 1 때에도 가져가는 실수를 저지름) 그래서 경로를 체그하는 v배열을 새로만들어 구현하였습니다.

 

2) 시간 복잡도

O(n^2)

 

3) 배운 점

문제를 제발 여러번 읽자

 

4) PS

문제를 제발 여러번 읽자

---

정답 코드

#include<bits/stdc++.h>
 
using namespace std;
const int MAX = 51;
int n, l, r;
int board[MAX][MAX];
int ret;
int moveY[] = {-1, 1, 0, 0};
int moveX[] = {0, 0, -1, 1};
 
int main() {
    cin >> n >> l >> r;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
 
    bool visited[MAX][MAX];
    while (1) {
        memset(visited, false, sizeof visited);
        bool flag = false;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(visited[i][j])
                    continue;
              
                vector<pair<int,int>> v;
                v.push_back({i, j});
                int pSum = board[i][j];
                int pCnt = 1;
 
                auto BFS = [&](){
                    queue<pair<int,int>> q;
                    q.push({i, j});
                    visited[i][j] = true;
                    while(!q.empty()){
                        auto [y,x] = q.front();
                        q.pop();
 
                        for(int d = 0; d < 4; d++){
                            int ny = y + moveY[d];
                            int nx = x + moveX[d];
 
                            if(ny < 0 || ny >= n || nx < 0 || nx >= n){
                                continue;
                            }
                            int diff = abs(board[y][x] - board[ny][nx]);
                            if(diff >= l && diff <= r && !visited[ny][nx]){
                                visited[ny][nx] = true;
                                q.push({ny, nx});
                                v.push_back({ny, nx});
                                pSum += board[ny][nx];
                                pCnt++;
                            }
                        }
                    }
                };
                BFS();
 
                if(pCnt >= 2){
                    flag = true;
                    for(int i = 0; i <v.size(); i++){
                        board[v[i].first][v[i].second] = pSum/pCnt;
                    }
                }
            }
        }
        if(flag)
            ret++;
        else
            break;
    }
 
    cout << ret << "\n";
}