[ 삼성 SW역량 평가 16234 ] 인구 이동 (C++)

[ 난이도 ]

★★☆

 

[ 문제 링크 ]

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

 

[ 문제 풀이 ]

본인은 BFS로 문제를 해결하였다. 문제의 조건은 다음과 같다.

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

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (1 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

 

문제 예시

이 문제를 해결하기 위해서 우선 모든 좌표에 대해서 BFS를 실행하였다 위 문제를 예시로 들면 (1,1)에서 조건에 맞는 국가를 모두 큐에넣고 Vector에 해당 국가의 좌표와 값을저장하여 (1,1)와 조건이 맞는 국가 (1,2),(2,1),(2,2)의 평균을 모두 구한후 모두 평균값으로 해당 국가의 인구수를 대체 하였다. 그렇게 구해진 결과는 다음과 같다.

문제 예시

[ 소스 코드 ]

// 헤더 파일을 불러옴
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
 
// 맵의 크기는 최대 50+1
#define Max_Size 51
 
// 맵과 해당 맵에있는 인구를 나타냄
int Map[Max_Size][Max_Size];
int A[Max_Size][Max_Size];
 
// 각각 동,서,남,북임
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
 
// 방문 처리를 위한 배열
int Visit[Max_Size][Max_Size];
 
// Vector_cnt : 연합벡터가 몇개 있는 지 알려주는 지표
int Vector_cnt = 0;
 
// cnt : 정답의 개수
int cnt = 0;
 
// N: 맵의 크기 , L : 최솟값, R : 최댓값
int N, L, R;
 
// Union은 연합의 크기를 넉넉잡아 설정해야 RunTime Error를 피할 수 있음.
vector<pair<pair<int,int>,int>> Union[Max_Size*Max_Size];
 
// 입력을 받아오는 함수.
void Load_Input()
{
    cin >> N;
    cin >> L >> R;
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            cin >> A[i][j];
        }
    }
}
 
// 해당 Number의 연합을 초기화 시켜줌
void Reset_Union(int number)
{
    while (!Union[number].empty())
    {
        Union[number].pop_back();
    }
}
 
// 전체 연합을 초기화 시킴
void Total_Reset_Union()
{
    for (int i = 0; i < Vector_cnt; ++i)
    {
        while (!Union[Vector_cnt].empty())
        {
            Union[Vector_cnt].pop_back();
        }
    }
    Vector_cnt = 0;
}
 
// 인구이동을 하는 함수
void Move()
{
    // k : 해당 연합의 개수만큼 반복
    for (int k = 0; k < Vector_cnt; ++k)
    {
        // 합과 평균
        int sum = 0;
        int average = 0;
        // k번째 연합의 합을 구함
        for (int i = 0; i < (int)Union[k].size(); ++i)
        {
            int u_a = Union[k].at(i).second;
            sum = sum + u_a;
        }
        // k번째 연합의 평균을 구함
        average = sum / (int)Union[k].size();
 
        // k번째 연합의 좌표 정포를 받아와 average값을 덮어줌
        for (int j = 0; j < (int)Union[k].size(); ++j)
        {
            int u_x = Union[k].at(j).first.first;
            int u_y = Union[k].at(j).first.second;
            A[u_x][u_y] = average;
        }
    }
    // 연합의 개수가 없을경우 건너뛰고
    if (Vector_cnt == 0)
    {
        return;
    }
    // 연합의 개수가 1개 이상일경우 정답을 늘려줌
    else
    {
        cnt++;
    }
}
 
// 인구이동을 계속할지 안할지 여부를 알려주는 함수.
char Stop_Or_Continue()
{    
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {    
            // 동서남북으로 탐색하되 맵을 벗어나선 안됨
            for (int k = 0; k < 4; ++k)
            {
                int x = i;
                int y = j;
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (nx < 1 || nx > N || ny < 1 || ny >N)
                {
                    continue;
                }
                // 인구이동할 조건이 남아있으면 Continue
                if ( L <= abs(A[nx][ny] - A[x][y]) && abs(A[nx][ny] - A[x][y]) <= R)
                {
                    return 'C';
                }
            }
        }
    }
    // 아니라면 Stop
    return 'S';
}
 
// 한번 이동할 때 마다 방문기록을 초기화시켜줌
void Reset_Visit()
{
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            Visit[i][j] = 0;
        }
    }
}
 
// BFS를 모든 좌표에 적용시키고, 연합 끼리 뭉침
void BFS()
{
    queue<pair<pair<int, int>, int>> Q;
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            // 좌표를 입력하고
            Q.push(make_pair(make_pair(i, j), cnt));
            // 연합 정보를 매번 초기화 시켜준다.
            Reset_Union(Vector_cnt);
            // 연합 정보에 처음 좌표의 정보를 입력한다.
            Union[Vector_cnt].push_back(make_pair(make_pair(i, j), A[i][j]));
            // 초기 좌표 방문 처리
            Visit[i][j] = 1;
 
            // 큐가 빌때 까지(한 연합이 생성 되는과정)
            while (!Q.empty())
            {
                int x = Q.front().first.first;
                int y = Q.front().first.second;
                int z = Q.front().second;
                Q.pop();
                for (int k = 0; k < 4; ++k)
                {
                    // 동서남북 순으로 탐색
                    int nx = x + dx[k];
                    int ny = y + dy[k];
                    // 맵을 벗어나거나 조건이 맞지않다던가 방문했을경우 예외처리.
                    if (nx < 1 || nx > N || ny < 1 || ny >N)
                    {
                    
                        continue;
                    }
                    if (abs(A[nx][ny] - A[x][y]) < L || abs(A[nx][ny] - A[x][y]) > R)
                    {
                    
                        continue;
                    }
                    if (Visit[nx][ny] == 1)
                    {
                        
                        continue;
                    }
 
                    // 조건이 맞을경우 큐에 넣어주고 방문처리
                    Q.push(make_pair(make_pair(nx, ny), cnt));
                    Visit[nx][ny] = 1;
                
                    // Vector_cnt 번째 연합에 해당 국가를 추가함
                    Union[Vector_cnt].push_back(make_pair(make_pair(nx, ny), A[nx][ny]));
                }
            }
            // 그렇게 만들어진 연합이 초기 국가 포함 2개이상 있을경우 다음 연합을 만들러감
            if ((int)Union[Vector_cnt].size() > 1)
            {
                Vector_cnt++;
            }
        }
    }
    // 연합들이 만들어지면 이동을함
    Move();
    // 다음 이동을 위해 연합정보를 초기화 시킴
    Total_Reset_Union();
    // 다음 이동을 위해 방문 정보를 초기화 시킴.
    Reset_Visit();
}
 
int main()
{
    // 입력을 받아옵니다
    Load_Input();
    // 'S' 신호가 들어올때 까지 BFS를 시행합니다.
    while (1)
    {
        BFS();
        if (Stop_Or_Continue() == 'S')
        {
            break;
        }
    }
    cout << cnt;
 
    return 0;
}