백준 16234 인구 이동

이번에도 예제가 너무 많아서 사진은 다 넣지 않았다..

 

인구 이동 문제도 앞선 2문제와 같이 시뮬레이션 문제이다. 주어진 조건을 만족하도록 코딩하면 된다.

시뮬레이션 문제는 사용하는 언어를 얼만큼 숙련도 있게 다루는가가 중요한 것 같다. 아직 c++이 익숙하지 않아서 조금 힘들었다.

 

vector배열을 많이 사용해보지 않아서 저장하고 가져오는 방법이 혼란스러웠다.

또한, bfs를 사용하는데 visit를 설정하는 조건이 조금 까다로웠던 것 같다.

인구수가 l과 r사이에 없을 때, 연합 목록에 넣지는 않아도 visit는 true로 설정했었는데, 모든 배열을 돌기 위해서 l과 r사이에 없을 때 visit를 false로 두는 조건이 까다로웠다.

 

제시된 예제는 다 맞았는데 답안을 제출할 때 틀렸다고 나와서 디버깅하는데 시간이 오래 걸렸다.

 

각 국가를 돌면서, 연합 번호를 vector 배열의 index로 하여 저장하였다. 만약 연합이 없다면 값이 1이므로, vector 배열의 모든 값이 1이 된다면, 연합이 없다고 간주하고 loop를 종료하였다.

연합이 있다면 적어도 하나의 원소는 값이 1보다 크기 때문에, 평균을 계산하여 대입해 주었다.

이처럼 연합 번호를 붙여주는 방식이 주효했던 것 같다.

 

코드는 아래와 같다.(디버깅을 위한 출력을 주석으로 처리했다..)

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>
using namespace std;
 
int map[50][50];
bool visit[50][50];
//int uni[50][50];
 
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
 
int main(int argc, char** argv) {
    int n, l, r, ans =0;
    cin >> n >> l >> r;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &map[i][j]);
        }
    }
 
    //인구이동이 없을 때까지 무한 loop
    while (1) {
        //cnt는 연합 국가들의 번호
        int cnt = 0;
        //연합할 국가들을 저장할 vector
        vector<tuple<int,int>> uni[2500];
 
        //새로 연합을 해야 하므로 visit, uni를 초기화 해준다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                visit[i][j] = false;
                //uni[i][j] = -1;
            }
        }
 
        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                if (!visit[x][y]) {
                    queue<pair<int, int>> q;
                    q.push(make_pair(x, y));
                    visit[x][y] = true;
                    uni[cnt].push_back(make_tuple(x, y));
                    //uni[x][y] = cnt;
 
                    while (!q.empty()) {
                        int row = q.front().first;
                        int col = q.front().second;
                        q.pop();
 
                        for (int i = 0; i < 4; i++) {
                            int nr = row + dr[i];
                            int nc = col + dc[i];
 
                            if (nr < 0 || nr >= n || nc < 0 || nc >= n)continue;
                            //방문한 적 있으면 continue
                            if (visit[nr][nc])continue;
                            //인구 차이가 l과 r사이에 없으면 visit했다고 처리하지 않는다.
                            if (abs(map[row][col] - map[nr][nc]) < l || abs(map[row][col] - map[nr][nc]) > r) continue;
                            
                            uni[cnt].push_back(make_tuple(nr, nc));
                            //방문한 적 없으므로 queue에 넣는다.
                            visit[nr][nc] = true;
                            q.push(make_pair(nr, nc));
                        }
                    }
                    //bfs를 다 돌고나면 연합하나를 만든 것이기 때문에 cnt를 증가시켜 준다.
                    //주의할 점은 연합 없이 혼자만 있는 경우에도 uni값을 가진다는 것이다.
                    cnt++;
                }
                /*출력부분(디버깅)
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        printf("%d ", visit[i][j]);
                    }
                    printf("\n");
                }
                printf("\n");
                */
            }
        }
        //연합 만드는 것이 끝나면 평균을 내줘야 한다.
        int ok = true;
        //v의 모든 원소가 1이라면 연합이 없다는 것
        for (int i = 0; i < cnt; i++) {
            if (uni[i].size() > 1) {
                //1이상이면 연합이 있으니까 평균을 내준다.
                ok = false;
                int sum = 0;
                int count = 0;
                //v에서 찾아서 값을 더해준다.
                for (int j = 0; j < uni[i].size(); j++) {
                    int row, col;
                    tie(row, col) = uni[i][j];
                    sum += map[row][col];
                    count++;
                }
                //평균을 내고 대입해준다.
                int val = sum / count;
                for (int j = 0; j < uni[i].size(); j++) {
                    int row, col;
                    tie(row, col) = uni[i][j];
                    map[row][col] = val;
                }
            }
        }
 
        if (ok)break;
        /*출력부분(디버깅)
        printf("--------------%d번 째 인구이동 끝!!------------\n", ans);
        printf("이동 결과\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                printf("%d ", map[i][j]);
            }
            printf("\n");
        }
        printf("----------------------------------\n");
        */
        //인구이동이 있을 때마다 답을 증가
        ans++;
    }
 
    printf("%d\n", ans);
 
    return 0;
}