[백준 c++] 16234 인구 이동

문제 설명

https://www.acmicpc.net/problem/16234
N×N크기의 땅이 있고 각각의 땅에는 나라가 하나씩 존재한다. r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다.
인구 이동이 하루 동안 다음과 같이 진행될 때 인구 이동이 며칠동안 지속되는지 구하는 문제다.

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

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

아이디어

dfs로 전체 탐색하면서 인구이동의 조건을 만족하는 나라를 모두 방문처리 해주고, 값을 바꿔주는 식으로 풀었는데 제출 80%에서 시간초과가 났다.
dfs가 끝난 이후에 다시 맵을 전체 탐색(이중 for문)하면서 visited가 1인 나라들의 값을 바꿔줬는데 이런식으로 하면 시간초과가 나나보다.

그래서 dfs를 통해 방문처리된 나라들의 좌표를 vector pair에 저장하고
dfs끝나면 vector pair를 탐색하여(for문) 좌표의 나라들의 값을 바꿔주는 식으로 풀었더니 정답처리됐다.

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, l, r;
int a[51][51];
int visited[51][51];
int dy[4] = {1, 0, -1, 0};
int dx[4] = {0, -1, 0, 1};
int tmp, res;
vector<pair<int, int>> v;
void open(int y, int x, vector<pair<int, int>> &v)
{
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= n || nx >= n)
            continue;
        if (visited[ny][nx])
            continue;
        if (abs(a[y][x] - a[ny][nx]) >= l && abs(a[y][x] - a[ny][nx]) <= r)
        {
            visited[y][x] = 1;
            visited[ny][nx] = 1;
            v.push_back({ny, nx});
            tmp += a[ny][nx];
            open(ny, nx, v);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> l >> r;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
        }
    }

    while (1)
    {
        bool flag = 0;
        fill(&visited[0][0], &visited[0][0] + 51 * 51, 0);

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (visited[i][j] == 0)
                {
                    v.clear();
                    v.push_back({i, j});
                    tmp = a[i][j];
                    open(i, j, v);
                    if (v.size() == 1)
                        continue;
                    for (pair<int, int> b : v)
                    {
                        a[b.first][b.second] = tmp / v.size();
                        flag = 1;
                    }
                }
            }

            if (!flag)
                break;
            res++;
        }
        cout << res << "\n";
    }
}