Machineboy空
16235: 인구 이동 - DFS 본문
https://www.acmicpc.net/problem/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;
}
'Computer > Coding Test' 카테고리의 다른 글
12869 : 뮤탈리스크 - BFS, DP (1) | 2024.02.27 |
---|---|
4179 : 불! - BFS (1) | 2024.02.27 |
2589 : 보물섬 - BFS (0) | 2024.02.22 |
1068 : 트리 - DFS, 트리 (0) | 2024.02.22 |
15686 : 치킨 배달 - 조합(Combination), 브루트포스, 백트래킹 (0) | 2024.02.22 |