단순한 BFS 문제에서 조금 더 생각을 해야하는 문제였다.
총 3가지의 루틴을 반복한다.
1. 맵 처음과 끝까지 반복문을 돌며 BFS가 가능한 곳의 좌표를 찾는다.
2. BFS를 돌며 건에 해당하는 좌표들을 구해 맵의 값을 바꿔준 후 다시 BFS가 가능한 좌표를 찾는다.
3. BFS가 가능한 좌표를 찾지 못할 때까지 이를 반복한다.
solution()
함수의 코드를 보면 visit 배열과 isTrue()
함수를 사용하여 BFS가 가능한 지 확인을 한다. 처음 알고리즘 구상을 할 때 visit 만을 이용하면 될거라고 생각을 해 isTrue()
를 생각하지 않았고 당연히 시간 초과가 됐었다. 반복문 내에서 BFS를 사용할 때는 조건문을 만들 때 BFS 가능 유무도 추가될 수 있다는 점을 주의하자.
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int N, L, R, res = 0;
int A[51][51];
bool visit[51][51];
bool check = true;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
bool isTrue(int y,int x) {
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;
int dif = abs(A[y][x] - A[ny][nx]);
if (dif >= L && dif <= R) {
return true;
}
}
return false;
}
void findRes(int i, int j) {
queue<pair<int, int>> q;
queue<pair<int, int>> q2;
int sum = 0, cnt = 0;
visit[i][j] = true;
q.push({ i,j });
q2.push({ i,j });
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
sum += A[y][x];
cnt++;
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 (visit[ny][nx]) continue;
int dif = abs(A[y][x] - A[ny][nx]);
if (dif >= L && dif <= R) {
visit[ny][nx] = true;
q.push({ ny,nx });
q2.push({ ny,nx });
}
}
}
while (!q2.empty()) {
int y = q2.front().first;
int x = q2.front().second;
A[y][x] = sum / cnt;
q2.pop();
}
}
void solution() {
while (check) {
check = false;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!visit[i][j] && isTrue(i, j)) {
findRes(i, j);
check = true;
}
}
}
memset(visit, false, sizeof(visit));
if(check) res++;
}
cout << res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> L >> R;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> A[i][j];
}
}
solution();
return 0;
}