16234번 인구 이동

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

저번에 푼 코드 : http://hsdevelopment.tistory.com/116

SW 역량 테스트 대비할 겸, 다시 풀어보았다.

#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 N = 0, L = 0, R = 0;
 
int Map[51][51] = { 0, };
 
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
 
int sum = 0, moving = 0;
 
bool visit[51][51] = { false, };
 
bool calc = false;
 
vector<pair<int, int> > v;
 
void DFS(int r, int c)
{
    v.push_back({ r,c });
 
    visit[r][c] = true;
 
    sum += Map[r][c];
 
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
 
        if (y < 0 || y >= N || x < 0 || x >= N || visit[y][x] || abs(Map[r][c] - Map[y][x]) < L || abs(Map[r][c] - Map[y][x]) > R) continue;
 
        calc = true;
 
        DFS(y, x);
    }
}
 
int main(void)
{
    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)
    {
        int before = moving;
 
        calc = false;
 
        memset(visit, false, sizeof(visit));
 
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (!visit[i][j])
                {
                    v.clear();
 
                    sum = 0;
 
                    DFS(i, j);
 
                    if (v.size() == 1) continue;
                    
                    int avg = sum / v.size();
 
                    for (int d = 0; d < v.size(); d++) Map[v.at(d).first][v.at(d).second] = avg;
                }
            }
        }
 
        if (calc) ++moving;
 
        if (before == moving) break;
    }
 
    printf("%d\n", moving);
 
    return 0;
}