[백준 16234번 - 인구 이동] C++ 풀이

백준 16234번.

 

사용한 알고리즘

- bfs

 

구현은 빠르게 했는데 80%에서 계속 시간초과가 나서 좀 애먹었다ㅜ

bfs 호출 수를 줄이고, map 값 변경을 bfs 내부에 해줘서 시간초과 문제를 해결했다..

flag를 사용해서 주변에 인구차가 l 이상 r이하 나는 나라가 있으면 해당 (i,j) 에 대하여 bfs 한번 호출하고 바로 for 문을 빠져나오게 했다.

그리고 처음에는 bfs 다 끝나고 바깥에서 sum, cnt 값을 가지고 map 을 수정해줬는데 해당 작업을 bfs 안에서 하니 시간초과문제가 해결되었다.

#include <stdio.h>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;

vector<vector<int>> map;
vector<vector<int>> visited;
int n, l, r;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
int cnt = 0;
int sum = 0;
int ans = 0;

void bfs(int start_x, int start_y) {
	queue<pair<int, int>> q;
	q.push(make_pair(start_x, start_y));
	visited[start_x][start_y] = 1;
	cnt++;
	sum += map[start_x][start_y];
	while(!q.empty()) {
		int cur_x = q.front().first;
		int cur_y = q.front().second;
		q.pop();
		for(int i = 0; i < 4; ++i) {
			int next_x = cur_x + dx[i];
			int next_y = cur_y + dy[i];
			if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < n) {
				int diff = abs(map[cur_x][cur_y] - map[next_x][next_y]);
				if (diff >= l && diff <= r && visited[next_x][next_y] == 0) {
					visited[next_x][next_y] = 1;
					cnt++;
					sum += map[next_x][next_y];
					q.push(make_pair(next_x, next_y));
				}
			}
		}
	}
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			if (visited[i][j] == 1) {
				map[i][j] = sum / cnt;
				visited[i][j] = -1;
			}
		}
	}
	return;
}

int main() {
	scanf("%d %d %d", &n, &l, &r);

	map.assign(n + 1, vector<int>(n + 1, 0));
	//visited.assign(n + 1, vector<int>(n + 1, 0));

	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			scanf("%d", &map[i][j]);
		}
	}
	bool flag = true;
	while(flag) {
		flag = false;
		visited.assign(n + 1, vector<int>(n + 1, 0));
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < n ; ++j) {
				bool bFlag = false;
				if (visited[i][j] == 0) {
					for(int k = 0; k < 4; ++k) {
						int nx = i + dx[k];
						int ny = j + dy[k];
						if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
							continue;
						} else if (visited[nx][ny] == 0 && abs(map[i][j] - map[nx][ny]) >= l && abs(map[i][j] - map[nx][ny]) <= r) {
							flag = true;
							bFlag = true;
							break;
						}
					}
				}
				if (bFlag) {
					bfs(i, j);
					bFlag = false;
				}
				cnt = 0;
				sum = 0;
			}
		}
		if (flag)
			ans++;
	}
	printf("%d\n", ans);
	return 0;
}