16235: 인구 이동 - DFS

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

16234번: 인구 이동

문제요약

조건에 따라 인구 이동이 일어나는 횟수

 

난이도

Gold 4

---

풀이 포인트

• DFS, connected componet 문제임을 파악하기

---

REVIEW

 

우선, 2차원 좌표를 1차원으로 묶어서 생각하는 법을 생각하다가 어후 너무 복잡해져서

풀이를 관두었다..

 

정말 간단하게 생각하면 된다.

기존 DFS을 돌릴 때 육지라면 ( a[ny][nx] ==1 ) 이면 이동했던 것을

문제의 조건에 따라 차가 l이상 r이하라면 ( abs(a[ny][nx] - a[y][x]) >=l && abs(a[ny][nx] - a[y][x]))때 이동하면 된다.

 

이동 즉, DFS의 조건부분을 살짝만 바꿔 응용하면 되었던 문제..

너무나 어렵게 생각해서 도중에 포기해버렸다..

 

요즘 브루트 포스문제, 조합, 순열 등 풀이에 약간 머리를 많이 굴려야 하는 문제들을 풀다보니

풀이 시간이 한없이 늘어날때가 있는데 .. 최대한 효율적으로 시간 활용하며 풀어나가기!

---

CODE

#include <bits/stdc++.h>
using namespace std;

int visited[54][54], a[54][54], n, l, r, sum, cnt;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
vector<pair<int, int>> v;

void dfs(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 (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[ny][nx])
            continue;
        if (abs(a[ny][nx] - a[y][x]) >= l && abs(a[ny][nx] - a[y][x]) <= r)
        {
            visited[ny][nx] = 1;
            v.push_back({ny, nx});
            sum += a[ny][nx];
            dfs(ny, nx, v);
        }
    }
}

int main()
{
    cin >> n >> l >> r;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> a[i][j];
        }
    }
    while (true)
    {
        bool flag = 0;
        fill(&visited[0][0], &visited[0][0] + 54 * 54, 0);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (!visited[i][j])
                {
                    v.clear();
                    visited[i][j] = 1;
                    v.push_back({i, j});
                    sum = a[i][j];
                    dfs(i, j, v);
                    if (v.size() == 1)
                        continue;
                    for (pair<int, int> b : v)
                    {
                        a[b.first][b.second] = sum / v.size();
                        flag = 1;
                    }
                }
            }
        }
        if (!flag)
            break;
        cnt++;
    }
    cout << cnt << "\n";
    return 0;
}