728x90
16234번: 인구 이동
N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모
www.acmicpc.net
DFS로 풀었다. BFS나 DFS나 아무거나로 풀어도 된다.
DFS는 연합을 만드는 과정이다. 상하좌우 탐색하면서 l개 이상 r개 이하로 차이가 나면 스택에 넣어주었다.
탐색을 하면서 그 연합에 속하는 나라의 행과 열을 pair로 묶어서 countries라는 벡터에 넣어줬다.
또한 그 연합에 속하는 나라의 인구 수를 sum에 누적해서 더해줬다.
그렇게 연합을 만든 후에 sum을 countries.size()로 나눠서 인구 수를 갱신해주었다.
countries.size()가 1이면 인구 이동이 일어나지 않는 것이고 1보다 크면 인구 이동이 일어났다는 것이므로 flag = true로 해준다.
flag가 false라는 것은 더 이상 인구 이동이 일어나지 않는다는 것이므로 while문을 빠져나온다.
가장 바깥쪽 while문은 인구이동이 몇 번 일어났는지를 세어준다.
#include <iostream>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
int n, l, r;
cin >> n >> l >> r;
vector<vector<int>> v(n, vector<int>(n));
vector<vector<bool>> visited(n, vector<bool>(n, false));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> v[i][j];
}
}
int moveCount = 0;
while (true) {
visited = vector<vector<bool>>(n, vector<bool>(n, false));
bool flag = false;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!visited[i][j]) {
stack<pair<int, int>> stack;
stack.push(make_pair(i, j));
int sum = 0;
vector<pair<int, int>> countries;
while (!stack.empty()) {
pair<int, int> cur = stack.top();
stack.pop();
int row = cur.first;
int col = cur.second;
if (!visited[row][col]) {
visited[row][col] = true;
sum += v[row][col];
countries.push_back(cur);
if (row + 1 < n && abs(v[row][col] - v[row + 1][col]) >= l && abs(v[row][col] - v[row + 1][col]) <= r) {
stack.push(make_pair(row + 1, col));
}
if (row - 1 >= 0 && abs(v[row][col] - v[row - 1][col]) >= l && abs(v[row][col] - v[row - 1][col]) <= r) {
stack.push(make_pair(row - 1, col));
}
if (col + 1 < n && abs(v[row][col] - v[row][col + 1]) >= l && abs(v[row][col] - v[row][col + 1]) <= r) {
stack.push(make_pair(row, col + 1));
}
if (col - 1 >= 0 && abs(v[row][col] - v[row][col - 1]) >= l && abs(v[row][col] - v[row][col - 1]) <= r) {
stack.push(make_pair(row, col - 1));
}
}
}
if (countries.size() > 1) {
flag = true;
for (int k = 0; k < countries.size(); k++) {
int row = countries[k].first;
int col = countries[k].second;
v[row][col] = sum / countries.size();
}
}
}
}
}
if (!flag)
break;
moveCount++;
}
cout << moveCount;
return 0;
}
728x90
'알고리즘 문제' 카테고리의 다른 글
| [백준] 13460번 구슬 탈출 2 (0) | 2021.01.20 |
|---|---|
| [백준] 2458번 키 순서 (0) | 2021.01.19 |
| [백준] 1339번 단어 수학 (0) | 2021.01.18 |
| [백준] 5014번 스타트링크 (0) | 2021.01.18 |
| [백준] 12100번 2048 (Easy) (0) | 2021.01.18 |
