문제 정보
백준 ( BOJ ) 16234 인구 이동
문제 풀이 : bfs
문제 출처 : https://www.acmicpc.net/problem/16234
시작 Thinking
간단한 bfs 문제입니다.
늘 사용하던 방식에서, 방문 가능한지 체크 하는 부분만 추가 해 주시고,
값을 바꿔주는 것만 하면 됩니다.
visitied 만 신경 써 주세요.
매번 초기화를 해 줘야 합니다.
여기서 vector의 단점이 들어납니다..
같은 알고리즘이더라도, 백터는 초기화 속도가 매우 느려요.
그래서 가능하시다면, 백터 말고 배열로 설정해서, memset 을 이용 해 주시는게 속도가
잘 나올 겁니다.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, l, r;
int moveCount = 0;
int befCount = -1;
vector<vector<int>> country;
vector<vector<int>> visited;
vector<pair<int, int>> group;
void resetVisited() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
visited[i][j] = 0;
}
}
}
bool checkBoundary(int y, int x, int m) {
if (y < 0 || x < 0)
return false;
if (y >= n || x >= n)
return false;
if (visited[y][x] == 1)
return false;
if (abs(country[y][x] - m) >= l && abs(country[y][x] - m) <= r)
return true;
return false;
}
void bfs(int y, int x) {
int count = 1;
int m = 0;
int sum = 0;
queue<pair<int, int>> checkGroup;
checkGroup.push(make_pair(y, x));
group[0] = make_pair(y, x);
visited[y][x] = 1;
while (!checkGroup.empty()) {
y = checkGroup.front().first;
x = checkGroup.front().second;
m = country[y][x];
checkGroup.pop();
y--;
if (checkBoundary(y, x, m)) {
checkGroup.push(make_pair(y, x));
group[count] = make_pair(y, x);
count++;
visited[y][x] = 1;
}
y += 2;
if (checkBoundary(y, x, m)) {
checkGroup.push(make_pair(y, x));
group[count] = make_pair(y, x);
count++;
visited[y][x] = 1;
}
y--;
x--;
if (checkBoundary(y, x, m)) {
checkGroup.push(make_pair(y, x));
group[count] = make_pair(y, x);
count++;
visited[y][x] = 1;
}
x += 2;
if (checkBoundary(y, x, m)) {
checkGroup.push(make_pair(y, x));
group[count] = make_pair(y, x);
count++;
visited[y][x] = 1;
}
}
if (count > 1) {
if(moveCount == befCount)
moveCount++;
for (int i = 0; i < count; i++) {
sum += country[group[i].first][group[i].second];
}
for (int i = 0; i < count; i++) {
country[group[i].first][group[i].second] = sum / count;
}
}
}
int main() {
int temp;
cin >> n >> l >> r;
country.assign(n, vector<int>(n, 0));
visited.assign(n, vector<int>(n, 0));
group.assign(2500, make_pair(0, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> temp;
country[i][j] = temp;
}
}
while (moveCount != befCount) {
befCount = moveCount;
resetVisited();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (visited[i][j] == 0)
bfs(i, j);
}
}
}
cout << moveCount;
/*for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << country[i][j] << " ";
}
cout << endl;
}*/
return 0;
}
후기
소요 시간 : 26분
난이도 : 쉬운편