• Home
  • About
    • 코드좀비 photo

      코드좀비

      An amazing website.

    • Learn More
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[BOJ] 백준 16234 인구 이동 간단한설명과 코드 C++

04 Apr 2020

Reading time ~2 minutes

문제 정보

백준 ( 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분

난이도 : 쉬운편



백준C++bfs Share Tweet +1