[C++] 백준 16234번: 인구 이동

🔗 문제

 

16234번: 인구 이동

16234번: 인구 이동

 

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

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

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

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

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

 

 

🖍 풀이

 

반복문을 무한으로 돌리고 인구 이동을 더 이상하지 않으면 종료시켜야 겠다는 생각이 들것이다.

반복문을 종료시킬 플래그로 keep을 사용하였다.

 

 

while(keep)

• NxN 모든 구역을 탐색해야한다. → 2중 포문 사용
  • 사방에 연합 가능한 국가가 있다면?
    • BFS로 연합 가능한 범위를 탐색한다.
    • 인구 이동을 했음을 표시한다. (keep = true)
• 인구 이동한 흔적이 없다면 (keep == false) 반복문을 종료한다.
• 인구 이동 흔적이 있다면 (keep == true) ++answer하고 반복한다.

 

 

+ 재방문 확인

 

자세한 건 코드를 보면 되는데 위처럼 간단히 논리를 만들어 놓고 map의 visited 확인 체크를 잘못해서 헤맸었다. 

함수에 checkCondition()에 부합하는 것만 visited[][] = true를 해야한다는 점을 깨닫느라 시간을 많이 쓰게 되었다..

 

 

+ 연합 계산

 

queue<pair<int, int>> tmp 에 연합국의 좌표를 저장하고, 탐색이 끝난 후 tmp에 저장된 국가의 인구 수를 변경해주었다. 

이 방식으로 이중포문으로 완전 탐색을 하지 않아 시간을 줄일 수 있다. 

 

 

 

 

💾  소스

#include <iostream>
#include <queue>
#include <memory.h>
#include <cmath>

const int MAX = 50 + 1;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};

int N, L, R, answer = 0;
int map[MAX][MAX]; // 인구 수
bool visited[MAX][MAX] = {false, };

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=N || y>=N)
        return false;
    return true;
}

bool checkConditon(const int _x, const int _y, const int _d)
{
    int x = _x + dx[_d];
    int y = _y + dy[_d];
    
    if(!isValid(x, y) || visited[x][y])
        return false;
    
    int gap = std::abs(map[_x][_y] - map[x][y]);
    if(gap <= R && gap >= L)
        return true;
    
    return false;
}

void BFS(const int i, const int j)
{
    int population = 0;
    
    typedef std::pair<int, int> pii;
    std::queue<pii> q, unions;
    q.push({i, j});
    unions.push({i, j});
    
    visited[i][j] = true;
    
    while(!q.empty())
    {
        int nowX = q.front().first;
        int nowY = q.front().second;
        q.pop();
        
        population += map[nowX][nowY];

        for(int d=0; d<4; ++d)
        {
            if(checkConditon(nowX, nowY, d))
            {
                visited[nowX + dx[d]][nowY + dy[d]] = true;
                q.push({nowX + dx[d], nowY + dy[d]});
                unions.push({nowX + dx[d], nowY + dy[d]});
            }
        }
    }
    
    int tmp = population / unions.size();
    while(!unions.empty())
    {
        map[unions.front().first][unions.front().second] = tmp;
        unions.pop();
    }

}

int main()
{
    std::cin >> N >> L >> R;
    
    for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            std::cin >> map[i][j];
    
    while(1)
    {
        bool keep = false;
        for(int i=0; i<N; ++i)
        {
            for(int j=0; j<N; ++j)
            {
                if(visited[i][j])
                    continue;
                
                for(int d=0; d<4; ++d)
                {
                    if(checkConditon(i, j, d))
                    {
                        BFS(i, j);
                        keep = true;
                        break;
                    }
                }
            }
        }
        
        if(keep)
        {
            answer++;
            memset(visited, false, sizeof(visited));
        }
        else
            break;
    }
    
    std::cout << answer;
    
    return 0;
}