인구이동_16234

문제 출처 :인구이동_16234

파라미터 정리

전체 NxN 크기의 땅에 땅 1칸은 1x1크기를 가짐
r행 c열에 있는 칸에는 A[r][c]명의 인구 有
인구 이동은 더이상 발생하지 않을때까지 반복
인구이동 조건
-인구수 차이가 L이상 R이하라면 국경선이 한번 열림
-가능한 모든 국경선이 열렸을 때, 인구 이동을 시작함
-연합 = 국경선이 열려있는 나라들의 모임
-각 칸의 인구수 = (연합 인구수)/(연합을 이루고 있는 나라 개수) (소수점은 버림)
-인구이동 후, 연합 해체 및 국경선은 다시 닫힘

간략한 과정

input_1 N,L,R 입력받기 (1~N~50, 1~L,R~100)
input_2 초기 맵의 인구 수 A[r][c] 입력받기 (0~A[r][c]~100)
초기(0,0)과 오른쪽 칸의 값 비교하기
L~R사이의 범위에 들면 벡터에 {row,col,인구수} 정보를 푸쉬하고, 오른쪽 칸의 오른쪽 칸 비교하기
비교하는 값이 L~R사이의 값을 벗어나거나 주어진 NxN을 벗어날때까지
벗어날 경우 바로 직전 칸으로 돌아와 상,하,좌에 해당하는 값도 비교하기
이때 방문했던 곳은 따로 bool Map을 만들어서 true로 표시해두기
초기(0,0)으로 돌아오면 벡터의 처음부터 끝까지 인구수를 모두 더하고 벡터의 사이즈만큼 나눈 값을 벡터에 있는 row,col에 넣어주기
이때 cnt++;
벡터 초기화하고 방문한적 없는 다음 초기값을 찾아서 실행해줌
모든 Map이 ture가 될때까지 실행하기
모든 Map이 true면 다시 모두 false로 바꾼 후 재실행하기
이때 cnt != 0이면 res++;
모든 Map이 true인데 cnt가 0일 경우 인구이동이 발생할 수 없으므로 res값 반환하기
output 인구 이동이 발생하는 횟수 res를 출력하기 (출력 횟수는 2000번 이하)

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct country{
  int r, c;  
};

int N,L,R;
int A[50][50];//초기 인구수
bool visited[50][50];
int sum;
int Dr[4] = {0,1,0,-1};
int Dc[4] = {1,0,-1,0};
vector<country> combi;


void find(int row, int col, int dir){
    int nr = row + Dr[dir], nc = col + Dc[dir];
    if(visited[nr][nc] == true) return; //이미 방문해서 조사가 끝난 지역
    if(nr < 0 || nc < 0 || nr > N-1 || nc > N-1) return; //범위 벗어났을 때

    int temp = abs(A[row][col] - A[nr][nc]);
    if(temp >= L && temp <= R){
        combi.push_back({nr, nc});
        sum += A[nr][nc];
        for(int i = 0; i < 4; i++){ //현재 셀의 4방향에 대해서 조사
            visited[nr][nc] = true;
            find(nr, nc, i);
        }
    }
    return;
}

int solve(){
    int res = 0;
    bool flag;
    
    do{
        flag = false;
        //모든 셀 방문하지 않은 것으로 초기화
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                visited[i][j] = false;
        
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){//방문하지 않은 셀
                if(!visited[i][j]){
                    sum = A[i][j];
                    visited[i][j] = true;
                    combi.push_back({i,j});
                    
                    for(int k = 0; k < 4; k++)
                        find(i,j,k);
                        
                    if(sum != A[i][j]){//인구이동할 나라가 2개 이상일 때
                        int c_size = combi.size();
                        int num = sum/c_size;
                        
                        for(int t = 0; t < c_size; t++){
                            int row = combi[t].r, col = combi[t].c;
                            A[row][col] = num;
                            flag = true;
                        }
                    }
                    combi.clear();
                }
            }
        }
        
        if(flag) res++;
    }while(flag);
    
    return res;
}

int main()
{
    cin >> N >> L >> R;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            cin >> A[i][j];
            
    cout <<  solve() << endl;
    
    return 0;
}

다른 버전

백업_210418_pm_03:46

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct country{
    int r,c;  
};

int N,L,R;
int mapInfo[50][50];
bool visitedMap[50][50];
int sum;
vector<country> combiList;
//좌 상 우 하
int dr[4] = {0,-1,0,1};
int dc[4] = {-1,0,1,0};


void checkAround(int row, int col, int dir){
    int nr = row + dr[dir], nc = col + dc[dir];
    if(visitedMap[nr][nc]) return;
    if(nr < 0 || nc < 0 || nr > N-1 || nc > N-1) return;
    
    int temp = abs(mapInfo[nr][nc] - mapInfo[row][col]);
    if(temp >= L && temp <= R){
        combiList.push_back({nr, nc});
        sum += mapInfo[nr][nc];
        visitedMap[nr][nc] = true;
        
        for(int i = 0; i < 4; i++){
            checkAround(nr,nc,i);
        }
    }
    return;
}

int solve(){
    int cnt = 0;
    bool endFlag;
    //여러번 반복하기
    do{
        //다음 턴 방문 표시 초기화
        endFlag = true;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                visitedMap[i][j] = false;
                
        for(int i = 0; i < N; i ++){
            for(int j = 0; j < N; j++){
                if(!visitedMap[i][j]){
                    //1. 방문하지 않은 국가
                    combiList.push_back({i,j});
                    sum = mapInfo[i][j];
                    visitedMap[i][j] = true;
                    
                    //2. 연합 국가 조사하기
                    for(int k = 0; k < 4; k++)
                        checkAround(i,j,k);
                    
                    //3. 연합국 인구수 나누기
                    if(combiList.size() > 1){
                        int cSize = combiList.size();
                        int cNum = sum/cSize;
                        
                        for(int t = 0; t < cSize; t++){
                            int row = combiList[t].r, col = combiList[t].c;
                            mapInfo[row][col] = cNum;
                            endFlag = false;
                        }
                    }
                    //연합국 초기화
                    combiList.clear();
                }
            }
        }
       if(!endFlag) cnt++;
    }while(!endFlag);
    
    return cnt;
}

int main()
{
    cin >> N >> L >> R;
    for(int i = 0 ; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> mapInfo[i][j];
        }
    }
    cout << solve() << endl;
    
    return 0;
}