BOJ 16234 - 인구 이동

www.acmicpc.net/problem/16234

16234번: 인구 이동

 

이문제를 처음 풀때는 BFS 를 수행하면서

두 국가의 인구수 차이가 L 이상 R 이하인 (즉, 국경선을 열수있는) 국가들에게 동일한 번호의 라벨을 부여하여

BFS 가 끝나면, 각 라벨 번호에 맞는 인구수 총합 / 국가의 갯수로 배열을 갱신해주었다.

그러나 80% 정도에서 시간초과가 나서 통과하지 못했다.

(아래의 코드가 통과 못한 코드)

- c++

 

#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
 
#define MAX 52
#define INF 987654321
 
using namespace std;
 
int N, L, R, answer, cnt, sum;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int map[MAX][MAX];
bool visited[MAX][MAX];
vector<pair<int, int>> vec; 
 
void bfs(int r, int c) {
    queue<pair<int, int>> q;
    q.push({r, c});
    visited[r][c] = true;
    
    while(!q.empty()) {
        int y = q.front().first, x = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; ++i) {
            int ny = y + dy[i], nx = x + dx[i], diff = abs(map[ny][nx] - map[y][x]);
            if (ny < 0 || ny > N + 1 || nx < 0 || nx > N + 1) continue;
            if (L <= diff && diff <= R && !visited[ny][nx]) {
                visited[ny][nx] = true;
                q.push({ny, nx});
                sum += map[ny][nx]; cnt++;
                vec.push_back({ny, nx}); 
            }
        }
    }
}
 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> L >> R;
    
    memset(map, INF, sizeof(map));
    for (int i = 1; i <= N; ++i) 
        for (int j = 1; j <= N; ++j) 
            cin >> map[i][j];
 
    while(1) {
        bool flag = false;
        memset(visited, false, sizeof(visited));
        
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j){
                if (!visited[i][j]) {
                    sum = map[i][j]; cnt = 1;
                    vec.clear();
                    vec.push_back({i, j});
                    bfs(i, j);
                    if (cnt >= 2) {
                        for (int i = 0; i < vec.size(); ++i) {
                            map[vec[i].first][vec[i].second] = sum / cnt;
                            flag = true;    
                        } 
                    }
                }
            } 
        }
        
        if(flag) answer++;
        else break;
    }
    
    cout << answer;
    
    return 0;
}

 

위 코드를 보면 아래의 이부분이 시간초과의 주범이었는데

 

while(1) {
 // 윗 부분 생략
    for (int k = 0; k < vec.size(); ++k)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                if (label_map[i][j] == vec[k].first.first)
                    copy_map[i][j] = vec[k].first.second / vec[k].second;            
}

 

 

인구 이동이 발생하는 최대 횟수는 2000번 이며,

( while(1) 이 최대 2000번 수행 가능 )

위에서 설정한 vec 벡터는 각 연합국의 라벨번호와 인구수 총합 그리고 국가의 갯수를 담고 있었다.

따라서 최대 가능한 연합국의 수가 N * N 이 되고 (N * N 행렬의 모든 국가가 연합이 이뤄지지 않을때)

i, j 를 값으로 하는 아래의 이중 포문이 더해져서

O(2000 * N * N * N * N) 이 되버리는 코드가 되었기 때문이었다.

 

또한 copy_,map 배열과 label_map 선언도 모두 불필요한 메모리 낭비 였다.

 

 

이런 방식 대신 아래와 같이 코드를 간략화하여 시간초과 문제를 해결하려 하였다.

- c++

 

#include <cmath>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
 
#define MAX 52
#define INF 987654321
 
using namespace std;
 
int N, L, R, answer, cnt, sum;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
int map[MAX][MAX];
bool visited[MAX][MAX];
vector<pair<int, int>> vec; 
 
void bfs(int r, int c) {
    queue<pair<int, int>> q;
    q.push({r, c});
    visited[r][c] = true;
    
    while(!q.empty()) {
        int y = q.front().first, x = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; ++i) {
            int ny = y + dy[i], nx = x + dx[i], diff = abs(map[ny][nx] - map[y][x]);
            if (ny < 0 || ny > N + 1 || nx < 0 || nx > N + 1) continue;
            if (L <= diff && diff <= R && !visited[ny][nx]) {
                visited[ny][nx] = true;
                q.push({ny, nx});
                sum += map[ny][nx]; cnt++;
                vec.push_back({ny, nx}); 
            }
        }
    }
}
 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> L >> R;
    
    memset(map, INF, sizeof(map));
    for (int i = 1; i <= N; ++i) 
        for (int j = 1; j <= N; ++j) 
            cin >> map[i][j];
 
    while(1) {
        bool flag = false;
        memset(visited, false, sizeof(visited));
        
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j){
                if (!visited[i][j]) {
                    sum = map[i][j]; cnt = 1;
                    vec.clear();
                    vec.push_back({i, j});
                    bfs(i, j);
                    if (cnt >= 2) {
                        for (int i = 0; i < vec.size(); ++i) {
                            map[vec[i].first][vec[i].second] = sum / cnt;
                            flag = true;    
                        } 
                    }
                }
            } 
        }
        
        if(flag) answer++;
        else break;
    }
    
    cout << answer;
    
    return 0;
}

 

라벨을 붙이는 방식대신, BFS 를 한번 수행하고 난 이후에, 국경선을 오픈한 국가가 2개 이상이면

인구 이동이 가능하다는 의미가 되고, 인구 재조정이 가능해진다.

인구 재조정을 위해서, BFS 를 한번 수행할때, 앞에서 봤던 vec 벡터처럼 

라벨번호, 인구수 총합, 국가의 총 갯수 가 아니라

해당 국가들의 좌표를 집어 넣어서 시간복잡도를 줄일 수 있었다.

 

다만 주의할것은 BFS 를 한번 수행할때마다, 국경선 갯수를 파악하므로, 

연합 국가의 총 인구수를 나타내는 변수 sum 과 연합내의 국가의 갯수를 의미하는 cnt

그리고 연합 내의 국가의 좌표를 나타내는 벡터 변수 vec 에 대해서 초기화 작업이 필요하다.

 

문제의 정답은 인구 이동의 횟수를 찾아내야 하므로, BFS 를 수행해서 

한번이라도 국경선을 오픈했다면 (cnt >= 2) answer 를 1증가 시켜야하고

아니면 프로그램을 종료한다.