[ 백준 16234 ] 인구이동 (C++)

백준의 인구이동(16234) 문제이다.

( 문제 바로가기 )

삼성전자 코딩테스트 기출문제이다..

[ 문제풀이 ]

1. 문제를 보면, BFS로 쉽게 해결할 수 있을 것 같지만 한 단계를 더 생각해 줘야 해결할 수 있는 문제이다.

   전체적인 풀이과정을 알아보자.

   1. 인구의 이동이 없을 때 까지 반복을 시켜준다.

      → 인구의 이동이 있었는지 없었는지 Check할 수 있는 변수가 필요하다.

   2. 인구 이동이 가능한 범위 내에 있는 값들에 대해서만 BFS를 통해서 인구이동을 시켜준다.

      → 인구 이동이 가능한 범위 내에 있는지 판별할 수 있는 함수가 필요하다.

   3. BFS내에서, 인구의 이동이 있었던 정점들만 따로 관리 및 표시 해주고, 값을 바꿔줘야 한다.

      → 인구 이동이 있었던 정점들만 따로 표시를 하던지, 저장을 해줘야 한다.

   < 풀이과정 1번 >

   본인은 Check라는 bool형 변수를 사용해서, 인구 이동이 있었으면 true로 표시, 없었으면 false로 표시하면서

   반복문을 관리해 주었다.

  

   < 풀이과정 2번 >

   본인은, 모든 정점에 대해서 탐색하면서,

   1. 아직 인구이동이 없었던 정점

   2. 해당 정점을 기준으로 상하좌우 값을 비교해서 인구이동이 일어날 수 있는 정점

   이 2가지 조건이 성립하면 BFS()를 호출하도록 구현해 주었다.

  

   < 풀이과정 3번 >

   BFS()함수 내에서, 인구 이동이 있었던 정점들의 값들은 바뀌어야 하므로, 이 정점들만 따로 관리할 수 있어야 한다.

   여러가지 방법이 있겠지만, 본인은 Queue를 하나 더 사용하였다.

   인구 이동이 일어날 수 있는 정점들에 대해서는 Queue에 저장해 주었고(본문 코드에서 Nq), BFS가 모두 진행된 후에

   따로 저장해둔 인구 이동이 일어날 수 있는 정점들에 대해서만 값을 모두 바꿔주었다.

   이 외에도, Visit배열의 값을 통해서 인구 이동이 일어난 정점인지 아닌지 판단할 수 있는 방법이 있을 것이다.

   문제 자체가 그리 어렵지는 않은데, 한 단계 더 응용할수 있어야 하는 문제인 것 같다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
 
#define endl "\n"
#define MAX 50
using namespace std;
 
int N, L, R;
int MAP[MAX][MAX];
int Visit[MAX][MAX];
int Country_Number;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
bool Check = true;
 
void Input()
{
    cin >> N >> L >> R;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
bool Can_Combination2(int x, int y)
{
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (L <= abs(MAP[x][y] - MAP[nx][ny]) && abs(MAP[x][y] - MAP[nx][ny]) <= R) return true;
        }
    }
    return false;
} 
 
bool Can_Combination(int x, int y, int xx, int yy)
{
    if (L <= abs(MAP[x][y] - MAP[xx][yy]) && abs(MAP[x][y] - MAP[xx][yy]) <= R) return true;
    return false;
}
 
void BFS(int a, int b)
{
    queue<pair<int, int>> Q, Nq;
    Q.push(make_pair(a, b));
    Nq.push(make_pair(a, b));
    Visit[a][b] = true;
    int Sum = 0;
    int Cnt = 0;
 
    while (Q.empty() == 0)
    {
        int x = Q.front().first;
        int y = Q.front().second;
        Q.pop();
 
        Sum = Sum + MAP[x][y];
        Cnt = Cnt + 1;                                           
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if (Visit[nx][ny] != 0) continue;
            if (Can_Combination(x, y, nx, ny) == true)
            {
                Visit[nx][ny] = 1;
                Q.push(make_pair(nx, ny));
                Nq.push(make_pair(nx, ny));
            }
        }
    }
 
    int Value = Sum / Cnt;
    
    while (Nq.empty() == 0)
    {
        int x = Nq.front().first;
        int y = Nq.front().second;
        Nq.pop();
        MAP[x][y] = Value;
    }
}
 
void Print()
{
    cout << "########################################" << endl;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (Visit[i][j] == 0)
            {
                cout << 0 << " ";
            }
            else
            {
                cout << Visit[i][j] << " ";
            }
        }
 
        cout << "\t\t";
        for (int j = 0; j < N; j++)
        {
            cout << MAP[i][j] << " ";
        }
        cout << endl;
    }
    cout << "########################################" << endl;
 
}
 
void Solution()
{
    int Day = 0;
    while (Check)
    {
        //Print();
        Check = false;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {                    
                if (Visit[i][j] == 0 && Can_Combination2(i,j) == true)
                {
                    BFS(i, j);
                    Check = true;
                }
            }
        }        
        if (Check == true) Day++;
        memset(Visit, false, sizeof(Visit));
 
    }
    cout << Day << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}