16234번 인구 이동

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

 

최근 다시 푼 코드 : https://hsdevelopment.tistory.com/226

2018년 하반기 삼성 SW 역량 테스트 문제이다.

 

하루에 인구 이동이 여러 번 발생할 수 있다는 것만 알면 나름 쉽게 풀 수 있는 문제이다.

 

즉, for문을 통해 조건에 맞는 국가들이 있으면 DFS 함수를 실행한다.

 

그리고, DFS 호출이 한 번 끝날 때 마다, 인구 이동을 시킨다.

 

위에 처럼 작성하였다.

 

참고로 visit(방문 여부)가 있기 때문에, 하루에 여러 번 인구 이동이 발생하여도 서로 영향을 끼치지 않는다.

 

(코드가 좀 더러워 보인다. 나중에 시간이 날 때, 좀 더 간결하게 고쳐보도록 해야겠다.)

 

 

 

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
int Map[51][51] = { 0, };
 
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, -1, 0, 1 };
 
int N = 0, L = 0, R = 0;
 
bool visit[51][51] = { false, };
bool isStop = true;
 
int cnt = 0;
int sum = 0;
 
vector<pair<int, int> > v;
 
void DFS(int r, int c)
{
    visit[r][c] = true;
 
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            int row = r + dy[i];
            int column = c + dx[i];
 
            if (visit[row][column] || row >= N || row < 0 || column >= N || column < 0) continue;        
 
            int dist = abs(Map[row][column] - Map[r][c]);
 
            if (L <= dist && dist <= R)
            {
                sum += Map[row][column];
                ++cnt;
 
                isStop = false; // 인구 이동 계산 여부
 
                v.push_back({ row, column });
 
                DFS(row, column);
            }
        }
    }
}
 
int main(void)
{
    int result = 0;
 
    memset(Map, 0, sizeof(Map));
 
    scanf("%d %d %d", &N, &L, &R);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%d", &Map[i][j]);
        }
    }
 
    while (1)
    {
        isStop = true;
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (!visit[i][j])
                {            
                    sum = Map[i][j];
 
                    ++cnt;
 
                    v.push_back({ i,j });
 
                    DFS(i, j);
 
                    int avg = sum / cnt;
 
                    int Size = v.size();
 
                    for (int k = 0; k < Size; k++)
                    {
                        Map[v.at(k).first][v.at(k).second] = avg;
                    }
 
                    v.clear();
 
                    sum = 0;
                    cnt = 0;
                }
            }
        }
 
        memset(visit, false, sizeof(visit));
 
        if (isStop) break; 
        // isStop이 true라는 것은 더 이상 진행 X
 
        ++result;
    }
 
    printf("%d\n", result);
 
    return 0;
}