[BaekJoon/백준] 16234번 인구 이동

 

문제를 SCC를 구하는 문제로 재해석해 적절하게 풀이하였다.

 

문제에서 말하는 '연합' 은 두 개 이상의 나라가 합쳐졌을 때 말하는 표현이고

나의 알고리즘에서 '연합'은 SCC를 말한다. 즉 하나의 나라도 연합이라고 칭할 수 있게 해줬다.

 

그 용어 정의 차이만 있을 뿐, 문제를 푸는데 전혀 지장이 없다.

따라서 인구이동이 일어나지 않는 경우는, 모든 나라가 SCC이므로 SCC가 N * N개 일 때 종료하기만 하면 된다.

 

 

복잡하게 풀었을까봐 내심 걱정했는데, 찾아보니 그런건 아닌 것 같다.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int MAP[50][50];
int COP[50][50]; // SCC
bool VISIT[50][50];

int N, L, R;

int COR; // 연합 종류 (0부터 시작, 여기서의 연합은 문제와는 조금 다르게 SCC를 말하는 것으로 구현했음)
int DAYS; // 총 몇일 걸렸는가

int TOTAL_VAL, COUNT_VAL; // 각 연합의 평균값을 구하는 데 쓰임.

int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};


void dfs(int x, int y, int COR) { // SCC 0부터 시작.
    
    // 평균을 계산하기 위해 누적단계
    TOTAL_VAL += MAP[x][y];
    COUNT_VAL++;
    
    // 방문처리, SCC처리
    VISIT[x][y] = true;
    COP[x][y] = COR;
    
    
    for(int i = 0; i < 4; i++) {
        
        int tx = x + mx[i];
        int ty = y + my[i];
        
        if(tx < 0 || tx >= N || ty < 0 || ty >= N)
            continue;
        
        int val = abs(MAP[x][y] - MAP[tx][ty]);
        
        if(!VISIT[tx][ty] && val >= L && val <= R)
            dfs(tx, ty, COR);
    }
    
}


int main() {
    
    cin >> N >> L >> R;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++)
            cin >> MAP[i][j];
    }
    
    
    while(1) {
        
        vector<int> C; // 각 연합의 평균값 저장하는 벡터
        
        // 초기화
        memset(VISIT, 0, sizeof(VISIT));
        memset(COP, 0, sizeof(COP));
        COR = 0;

        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(!VISIT[i][j]) {
                    TOTAL_VAL = COUNT_VAL = 0;
                    dfs(i, j, COR++);
                    C.push_back(TOTAL_VAL / COUNT_VAL);
                }
            }
        }
        
        if(COR == N*N) // 각 나라가 SCC인 경우 = 각 나라가 연합인 경우 = 문제에서 말하는 연합이 없는 경우
            break;
        
        DAYS++;
        
        // 연합 값 업데이트
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++)
                MAP[i][j] = C[COP[i][j]];
        }
    }
    cout << DAYS << "\n";
}

 

 

소요 시간 : 1시간