백준 16234 인구 이동 C++

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

16234번: 인구 이동

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ16234.cpp

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

//
//  main.cpp
//  BJ16234
//
//  Created by 최화연 on 2022/03/28.
//

#include <iostream>
#include <queue>
using namespace std;

int N, L, R;
int A[100][100] = {0, };
int unity[100][100] = {0, };
int day = 0;

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

int open_border() {
    int cnt = 0;
    for(int r=0; r<2*N; r++) {
        for(int c=0; c<2*N; c++) {
            unity[r][c] = 0;
        }
    }
    for(int r=0; r<N; r++) {
        for(int c=0; c<N; c++) {
            unity[r*2][c*2] = 1;
            for(int d=0; d<4; d++) {
                int nr = 2*r+2*dy[d];
                int nc = 2*c+2*dx[d];
                if(nr < 0 || nr >= 2*N || nc < 0 || nc >= 2*N) continue;
                int differ = abs(A[r*2][c*2]-A[nr][nc]);
                if(L <= differ && differ <= R) {
                    unity[r*2+dy[d]][c*2+dx[d]] = 1;
                    cnt ++;
                }
            }
        }
    }
    return cnt;
}

void make_unity(int sr, int sc) {
    int p_num = A[sr][sc];
    int countries = 1;
    unity[sr][sc] = 2;
    queue<pair<int, int>> q;
    q.push({sr, sc});
    vector<pair<int, int>> loc;
    loc.push_back({sr, sc});
    while(!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        for(int i=0; i<4; i++) {
            int nr = r + dy[i];
            int nc = c + dx[i];
            if(nr < 0 || nr >= 2*N || nc < 0 || nc >= 2*N) continue;
            if(unity[nr][nc] == 1) {
                unity[nr][nc] = 2;
                if ((nr%2 + nc%2) == 0) {
                    p_num += A[nr][nc];
                    countries += 1;
                    loc.push_back({nr, nc});
                }
                q.push({nr, nc});
            }
        }
    }
    int new_num = p_num/countries;
    for(int i=0; i<loc.size(); i++) {
        A[loc[i].first][loc[i].second] = new_num;
    }
}

void get_unities() {
    for(int r=0; r<N; r++) {
        for(int c=0; c<N; c++) {
            if(unity[2*r][2*c] == 1) {
                make_unity(2*r, 2*c);
            }
        }
    }
}

void move_people() {
    while(true) {
        int border = open_border();
        if (border == 0) break;
        get_unities();
        day ++;
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> L >> R;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> A[i*2][j*2];
        }
    }
    
    move_people();
    cout << day << endl;
    
    return 0;
}

---

풀이 과정

풀이 시간 58분

 

#include <iostream>
#include <queue>
using namespace std;

int N, L, R;

#A[2*r][2*c] = (r, c) 나라의 인구수
int A[100][100] = {0, };

#unity[y][x] = 1 -> 경로가 있는 경우, 0 -> 경로가 없는 경우
int unity[100][100] = {0, };

#현재 일 수
int day = 0;

#좌, 상, 우, 하
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int open_border() {
    int cnt = 0;
    
    #국경선 초기화
    for(int r=0; r<2*N; r++) {
        for(int c=0; c<2*N; c++) {
            unity[r][c] = 0;
        }
    }
    
    for(int r=0; r<N; r++) {
        for(int c=0; c<N; c++) {
        	#(r, c) 나라인 칸 1로 셋팅
            unity[r*2][c*2] = 1;
            
            #인접한 4개 나라 탐색
            for(int d=0; d<4; d++) {
                int nr = 2*r+2*dy[d];
                int nc = 2*c+2*dx[d];
                
                #범위를 벗어난 경우, 무시한다
                if(nr < 0 || nr >= 2*N || nc < 0 || nc >= 2*N) continue;
                
                #두 나라의 인구 차이가 L이상 R이하인 경우, 국경선을 연다
                int differ = abs(A[r*2][c*2]-A[nr][nc]);
                if(L <= differ && differ <= R) {
                    unity[r*2+dy[d]][c*2+dx[d]] = 1;
                    cnt ++;
                }
            }
        }
    }
    return cnt;
}

void make_unity(int sr, int sc) {
	#연합의 총 인구수
    int p_num = A[sr][sc];
    #연합의 나라 수 
    int countries = 1;
    
    #연합의 시작 나라 2로 방문처리
    unity[sr][sc] = 2;
    
    queue<pair<int, int>> q;
    q.push({sr, sc});
    
    #연합의 모든 나라들의 위치를 담는 벡터
    vector<pair<int, int>> loc;
    loc.push_back({sr, sc});
    
    while(!q.empty()) {
        int r = q.front().first;
        int c = q.front().second;
        q.pop();
        
        #인접한 4칸 탐색
        for(int i=0; i<4; i++) {
            int nr = r + dy[i];
            int nc = c + dx[i];
            # 범위를 벗어난 경우, 무시한다
            if(nr < 0 || nr >= 2*N || nc < 0 || nc >= 2*N) continue;
            
            #국경선이 열려 있는 경우, 해당 칸을 탐색한다
            if(unity[nr][nc] == 1) {
                unity[nr][nc] = 2;
                
                #연합 나라인 칸인 경우, 인구 수와 나라 수를 카운팅하고, 해당 위치를 loc 벡터에 담는다
                if ((nr%2 + nc%2) == 0) {
                    p_num += A[nr][nc];
                    countries += 1;
                    loc.push_back({nr, nc});
                }
                q.push({nr, nc});
            }
        }
    }
    
    #연합을 이루는 각 나라의 인구 이동 후 인구 수 적용하기
    int new_num = p_num/countries;
    for(int i=0; i<loc.size(); i++) {
        A[loc[i].first][loc[i].second] = new_num;
    }
}

void get_unities() {
	#각 나라를 탐색한다
    for(int r=0; r<N; r++) {
        for(int c=0; c<N; c++) {
        	#새로운 연합인 경우, 해당 나라를 시작으로 연합의 모든 나라들을 탐색하고 인구를 이동시킨다
            if(unity[2*r][2*c] == 1) {
                make_unity(2*r, 2*c);
            }
        }
    }
}

void move_people() {
	#국경선이 열리면 계속 반복한다
    while(true) {
    	#국경선을 연다
        int border = open_border();
        
        #열린 국경선이 없다면, 종료한다
        if (border == 0) break;
        
        #인구를 이동시킨다
        get_unities();
        
        #현재 일 수 카운팅
        day ++;
    }
}

int main(int argc, const char * argv[]) {
    cin >> N >> L >> R;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> A[i*2][j*2];
        }
    }
    
    move_people();
    cout << day << endl;
    
    return 0;
}

#시간복잡도 = O(day*(2*N)^2) -> O(n), 공간복잡도 = O(n)

---

이전 풀이

풀이 시간 2시간 10분

//
//  main.cpp
//  BJ16234
//
//  Created by Hwayeon on 2021/08/05.
//

#include <iostream>
#include <cmath>
using namespace  std;
int N, L, R;
int A[50][50] ={0,};
int day = 0;

void move_population(){
	//각 나라의 연합 정보를 담는 배열
    int unity[50][50] = {0,};
    //연합 번호
    int u = 0;
    //연합 번호 별 정보 {연합 인구 수, 연합 국가 수}
    int unit[2501][2] = {0,};
    
    //1. 국경선 체크
    for(int y=0; y<N; y++){
        for(int x=0; x<N; x++){
        	//오른쪽 나라 위치 (r_x, r_y)
            int r_x = x+1;
            int r_y = y;
            
            //아래쪽 나라 위치 (b_x, b_y)
            int b_x = x;
            int b_y = y+1;
            
            //오른쪽 나라 체크
            if(r_x < N){
                int r_differ = abs(A[y][x]-A[r_y][r_x]);
                //오른쪽 나라와의 국경선을 오픈할 수 있는 경우,
                if(r_differ >= L && r_differ <= R){
                    //(r_x, r_y) 나라가 연합이 없는 경우,
                    if(unity[r_y][r_x] == 0){
                        //(x, y) 나라가 연합이 있는 경우, 연합 추가
                        if(unity[y][x] != 0){
                            unity[r_y][r_x] = unity[y][x];
                            unit[unity[y][x]][0] += A[r_y][r_x];
                            unit[unity[y][x]][1]++;
                        }
                        //(x, y) 나라가 연합이 없는 경우, 연합 생성
                        else{
                            u++;
                            unit[u][0] = A[y][x] + A[r_y][r_x];
                            unit[u][1] = 2;
                            unity[y][x] = u;
                            unity[r_y][r_x] = u;
                        }
                    }
                    //(r_x, r_y) 나라가 연합이 있는 경우,
                    else if(unity[y][x] != unity[r_y][r_x]){
                        //(x, y) 나라가 연합이 없는 경우, 연합 추가
                        if(unity[y][x] == 0){
                            unity[y][x] = unity[r_y][r_x];
                            unit[unity[r_y][r_x]][0] += A[y][x];
                            unit[unity[r_y][r_x]][1] ++;
                        }
                        //(x, y) 나라가 연합이 있는 경우, unity[y][x]로 연합을 합친다
                        else{
                            int before_u = unity[r_y][r_x];
                            unit[unity[y][x]][0] += unit[unity[r_y][r_x]][0];
                            unit[unity[r_y][r_x]][0] = 0;
                            unit[unity[y][x]][1] += unit[unity[r_y][r_x]][1];
                            unit[unity[r_y][r_x]][1] = 0;
                            //unity 정보 변경
                            int iy = y;
                            if(b_y < N) iy = b_y;
                            for(int i=0; i<=iy; i++){
                                for(int j=0; j<N; j++){
                                    if(unity[i][j] == before_u){
                                        unity[i][j] = unity[y][x];
                                    }
                                }
                            }
                        }
                    }
                    
                }
            }
            //아래쪽 나라 체크
            if(b_y < N){
                int b_differ = abs(A[y][x]-A[b_y][b_x]);
                //아래쪽 나라와의 국경선을 오픈할 수 있는 경우,
                if(b_differ >= L && b_differ <= R){
                    //(b_x, b_y) 나라가 연합이 없는 경우,
                    if(unity[b_y][b_x] == 0){
                        //(x, y) 나라가 연합이 있는 경우, 연합 추가
                        if(unity[y][x] != 0){
                            unity[b_y][b_x] = unity[y][x];
                            unit[unity[y][x]][0] += A[b_y][b_x];
                            unit[unity[y][x]][1]++;
                        }
                        //(x, y) 나라가 연합이 없는 경우, 연합 생성
                        else{
                            u++;
                            unit[u][0] = A[y][x] + A[b_y][b_x];
                            unit[u][1] = 2;
                            unity[y][x] = u;
                            unity[b_y][b_x] = u;
                        }
                    }
                    //(b_x, b_y) 나라가 연합이 있는 경우,
                    else if(unity[y][x] != unity[b_y][b_x]){
                        //(x, y) 나라가 연합이 없는 경우, 연합 추가
                        if(unity[y][x] == 0){
                            unity[y][x] = unity[b_y][b_x];
                            unit[unity[b_y][b_x]][0] += A[y][x];
                            unit[unity[b_y][b_x]][1] ++;
                        }
                        //(x, y) 나라가 연합이 있는 경우, unity[y][x]로 연합을 합친다
                        else{
                            int before_u = unity[b_y][b_x];
                            unit[unity[y][x]][0] += unit[unity[b_y][b_x]][0];
                            unit[unity[y][x]][1] += unit[unity[b_y][b_x]][1];
                            unit[unity[b_y][b_x]][0] = 0;
                            unit[unity[b_y][b_x]][1] = 0;
                            //unity 정보 변경
                            for(int i=0; i<=b_y; i++){
                                for(int j=0; j<N; j++){
                                    if(unity[i][j] == before_u){
                                        unity[i][j] = unity[y][x];
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    //연합이 없는 경우, 종료
    if(u == 0) return;
    
    //국경선을 하루 오픈한다
    day++;
    for(int i=1; i<=u; i++){
    	//i 연합이 있는 경우,
        if(unit[i][1] > 0){
        	//인구 이동
            int np = unit[i][0]/unit[i][1];
            for(int y=0; y<N; y++){
                for(int x=0; x<N; x++){
                    if(unity[y][x] == i){
                        A[y][x] = np;
                    }
                }
            }
        }
    }
    move_population();
}

int main(int argc, const char * argv[]) {
    cin >> N >> L >> R;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> A[i][j];
        }
    }
    move_population();
    cout << day << endl;
    return 0;
}
//시간복잡도 = O(n^5), 공간복잡도 = O(n^2)