[백준-삼성SW역량테스트 기출] 16234번. 인구 이동 C++

www.acmicpc.net/problem/16234

16234번: 인구 이동

>문제 설명

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

 

풀이

문제에서 주어진 예제이다.

문제를 보자마자 Union&find가 떠올라서 (쓸데없이..) 그렇게 풀이했다.

IDE에서 웬만하면 시간초과가 안나던데.. 이 코드는 시간초과가 나서 다시 생각했다.

 

다시 생각해보니 국경을 열 나라들의 부모 정보를 가지고 있을 필요가 없다.

한 구역과 다른 구역을 이어주는 애를 탐색했을 때, 그 두 그룹을 합쳐줘야한다고 생각해서 Union&Find가 생각났는데,

어차피 BFS로 탐색해주기 때문에 (i,j)에서 이을 수 있는 곳은 한 번의 BFS 탐색에 다 탐색된다.

따라서 Union&Find에서의 root노드가 당연히 (i,j)이다.

 

>틀린 코드

#define MAXN 52
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <string.h>
using namespace std;

int N, L, R;
int map[MAXN][MAXN];
int parent[MAXN*MAXN];
//int root[MAXN*MAXN];
int visited[MAXN][MAXN];
int numOfMove = 0;

pair<int,int> dir[4] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

int getParent(int x){
    
    if(parent[x] == x){
        return x;
    }
    else{
        int p = getParent(parent[x]);
        parent[x] = p;
        return p;
    }
}

void unionParent(int x, int y){
    
    x = getParent(x);
    y = getParent(y);
    
    if(x<y){
        parent[y] = x;
    }
    else{
        parent[x] = y;
    }
}

bool findParent(int x, int y){
    x = getParent(x);
    y = getParent(y);
    if(x==y){
        return true;
    }
    else{
        return false;
    }
}

void calcPopulation(){
    
    bool check[N][N];
    
    for(int i=0; i<N*N; i++){
        
        vector<pair<int,int>> open;
        int x = (int)i/N;
        int y = i%N;
        open.push_back({x, y});
        
        int sum = map[x][y];
        int country = 1;
        
        for(int j=i+1; j<N*N; j++){
            if(findParent(i, j) && !check[i][j]){
                check[i][j] = true;
                x = (int)j/N;
                y = j%N;
                open.push_back({x, y});
                sum += map[x][y];
                country++;
            }
        }
        
        for(int j=0; j<open.size(); j++){
            map[open[j].first][open[j].second] = (int)sum/country;
        }
    }
}

void solve(){
    
    while(true){
        
        bool ifMove = false;
        
        for(int i=0; i<N*N; i++){
            parent[i] = i;
        }
        
        
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                
                queue<pair<int,int>> q;
                q.push({i,j});
                visited[i][j] = true;
                
                while(!q.empty()){
            
                    int nowx = q.front().first;
                    int nowy = q.front().second;
                    q.pop();
            
                    for(int k=0; k<4; k++){
                        int nextx = nowx + dir[k].first;
                        int nexty = nowy + dir[k].second;
                
                        if(nextx>=0 && nextx<N && nexty>=0 && nexty<N && !visited[nextx][nexty]){
                    
                            int diff = abs(map[nowx][nowy] - map[nextx][nexty]);
                            if(diff >= L && diff <= R){
                                unionParent(nowx*N+nowy , nextx*N+nexty);
                                ifMove = true;
                                q.push({nextx, nexty});
                                visited[nextx][nexty] = true;
                            }
                        }
                    }
                }
            }
        }
        
        if(ifMove == false){
            break;
        }
        numOfMove++;
        
        //calculate new population
        calcPopulation();
        
        for(int i=0; i<N; i++){
            memset(visited[i], false, sizeof(visited[i]));
        }
    }

}

void initialize(){
    
    cin>>N>>L>>R;
    
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>map[i][j];
        }
    }
    
}

int main()
{
    
    initialize();
    
    solve();
    
    cout<<numOfMove<<"\n";
    
    return 0;
}

 

맞은 코드

2중 For문으로 (i,j)에서 국경을 열 나라(연합 가능국)들을 BFS 탐색한다.

연합 나라들 좌표를 toMove 벡터에 담아두고, 각 나라의 인구수를 sum 변수에 저장해둔다.

BFS가 끝나면 연합의 인구수를 다시 계산해준다 (calcPopulation() 함수)

연합이 하나도 존재하지 않았다면 이동한 횟수를 출력하고 종료한다.

#define MAXN 52
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <string.h>
using namespace std;

int N, L, R;
int map[MAXN][MAXN];
vector<pair<int,int>> toMove;
bool visited[MAXN][MAXN];
int numOfMove = 0;

pair<int,int> dir[4] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};


void calcPopulation(int sum, int count){
    
    for(int i=0; i<toMove.size(); i++){
        int x = toMove[i].first;
        int y = toMove[i].second;
        map[x][y] = (int)sum/count;
    }
    
}

void solve(){
    
    while(true){
        
        bool ifMove = false;
        
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                
                int sum = 0;
                int count = 0;
                
                if(visited[i][j] == true) continue;
                
                queue<pair<int,int>> q;
                q.push({i,j});
                toMove.push_back({i, j});
                visited[i][j] = true;
                sum += map[i][j];
                count++;
                
                while(!q.empty()){
            
                    int nowx = q.front().first;
                    int nowy = q.front().second;
                    q.pop();
            
                    for(int k=0; k<4; k++){
                        int nextx = nowx + dir[k].first;
                        int nexty = nowy + dir[k].second;
                
                        if(nextx>=0 && nextx<N && nexty>=0 && nexty<N && !visited[nextx][nexty]){
                    
                            int diff = abs(map[nowx][nowy] - map[nextx][nexty]);
                            if(diff >= L && diff <= R){
                                ifMove = true;
                                q.push({nextx, nexty});
                                toMove.push_back({nextx, nexty});
                                visited[nextx][nexty] = true;
                                sum += map[nextx][nexty];
                                count++;
                            }
                        }
                    }
                }
                
                //calculate new population
                if(toMove.size() > 1) calcPopulation(sum, count);
    
                toMove.clear();
                
            }
        }
        if(ifMove == false){
            break;
        }
        else numOfMove++;
        
        memset(visited, false, sizeof(visited));
    }

}

void initialize(){
    
    cin>>N>>L>>R;
    
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin>>map[i][j];
        }
    }
    
}

int main()
{
    
    initialize();
    
    solve();
    
    cout<<numOfMove<<"\n";
    
    return 0;
}