백준 18513 샘터 c++ (bfs)

문제 출처 : https://www.acmicpc.net/problem/18513

18513번: 샘터

문제

일직선 상의 공간에 N개의 샘터가 존재하며, K채의 집을 짓고자 한다. 모든 샘터 및 집이 존재하는 위치는 항상 정수 형태이다. 이때 일직선 상의 공간에서 N개의 샘터 및 K채의 집들은 모두 서로 다른 위치에 존재한다. 다시 말해 하나의 위치에는 샘터가 있거나, 집이 있거나, 혹은 아무것도 없다.

K채의 집을 지을 때, 가능하면 샘터의 주변에 집들을 지어서 K채의 모든 집에 대한 불행도의 합이 최소가 되도록 짓고자 한다. 이때 특정한 집에 대한 불행도란, 가장 가까운 샘터까지의 거리(Distance)로 정의된다. 예를 들어 특정한 집이 1에 위치하고, 그 집과 가장 가까운 샘터가 -5에 위치한다고 하면, 이 집의 불행도는 6이다.

N=2, K=5일 때, 모든 집에 대한 불행도의 합이 최소가 되도록 집을 짓는 경우를 고려해보자. 아래 그림과 같이 두 개의 샘터가 0, 3의 위치에 존재한다고 가정하자.

이때 다음과 같이 5채의 집을 설치하면, 각 집의 불행도의 합이 2+1+1+1+1=6로 최소가 된다. 집을 짓는 가능한 경우의 수는 여러 가지가 될 수 있지만, 불행도의 합을 6보다 작게 만드는 방법은 없다.

입력

첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ 100,000,000) 단, 모든 N개의 샘터의 위치들은 서로 다르게 주어진다.

출력

첫째 줄에 모든 집에 대한 불행도의 합의 최솟값을 출력한다.

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

풀이

우선 문제에서 그래프의 범위가 명확히 나와있진 않지만,

샘터의 범위를 통해 집을 지을 수 있는 그래프의 범위를 유추할 수 있다.

샘터는 -1억부터 1억까지 위치할 수 있고, -1억에 샘터가 위치할 경우,

집은 샘터까지의 거리를 최소화하려면 샘터의 양쪽으로 지어나가야 하기 때문에

-1억 5만까지 지을 수 있다. 반대로 1억에 샘터가 위치할 때도 마찬가지로 1억 5만까지 지을 수 있다.

 

샘터의 위치를 bfs의 시작점으로 큐에 입력하고, 각 샘터의 위치에서 bfs를 해가며 거리를 더하면 된다.

이때 한 싸이클(bfs의 한 턴)인 큐의 사이즈를 따로 저장해놓고, 싸이클 만큼 bfs를 돌린다.

//첫 번째 턴에선 샘터와의 거리가 1인 집을 짓는다.

//두 번째 턴에선 샘터와의거리가 2인 집을 짓는다.

// ~~~

 

bfs를 돌 땐, 이미 집을 지은 곳은, visited에 true로 표시를 해줘야 하며, 집을 k개 만큼 지었으면 프로그램을 종료한다.

result는 int의 범위를 초과하니 long long으로 선언해줘야 한다. 

코드 1처럼 visited 배열을 이용할 땐, 배열의 인덱스는 음수가 될 수 없으니, 위치가 음수일 때의 visitedM배열을 만들어 수에 -를 붙여 인덱스를 다루자.

 

set을 이용한 풀이에선 음수 양수 신경 쓸 필요 없이, 그냥 set에 값이 들어있지 않으면 탐색(집 짓기)을 계속 진행하면 된다. unorder_set과 set을 이용한 풀이의 시간 차이를 보면 set과 unordered_set의 차이를 실감할 수 있다.

/*

  set은 정렬되어 있는 상태에서 탐색을 하므로 O(logN)의 시간이 걸린다.

  unordered_set은 해시 함수로 탐색을 하기 때문에 평균적으로 O(1)의 상수 시간이 걸린다.

  다만 원소의 개수가 많을수록 해시충돌이 일어날 확률이 높아지고,

  최악의 경우 O(N)으로 set보다 오래 걸리는 경우가
  있기 때문에,
  원소의 개수가 적고 빠른 성능을 원하면 unordered_set,
  원소의 개수가 많고 안정성을 원하면 set을 사용하자!

  이 문제를 통해 원소의 개수가 10만 개면 적은 편이구나.. 생각했다.

*/

코드1(visited배열)

#include <iostream>
#include <queue>
using namespace std;

//위치가 양수일 때
bool visitedP[100050001];
//위치가 음수일 때
bool visitedM[100050001];
int n, k;
int dir[2] = { 1,-1 };
queue<int> q;
long long result;
void bfs() {
	int dis = 0;
	while (!q.empty()) {
		int size = q.size();
		dis++;
		for (int i = 0; i < size; i++) {
			int cur = q.front();
			
			q.pop();

			for (int j = 0; j < 2; j++) {
				int next = cur + dir[j];
				if (next < 0) {
					if (!visitedM[-next]) {
						visitedM[-next] = true;
						q.push(next);
						result += dis;
						if (--k == 0) {
							return;
						}
					}
				}
				else {
					if (!visitedP[next]) {
						visitedP[next] = true;
						q.push(next);
						result += dis;
						if (--k == 0) {
							return;
						}
					}
				}
			}
		}
	}

}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (a < 0) {
			visitedM[-a] = true;
		}
		else {
			visitedP[a] = true;
		}
		q.push(a);
	}
	bfs();
	cout << result;
	return 0;
}

코드2(set)

#include <iostream>
#include <queue>
#include <set>
using namespace std;


set<int> se;
int n, k;
int dir[2] = { 1,-1 };
queue<int> q;
long long result;
void bfs() {
	int dis = 0;
	while (!q.empty()) {
		int size = q.size();
		dis++;
		for (int i = 0; i < size; i++) {
			int cur = q.front();
			q.pop();

			for (int j = 0; j < 2; j++) {
				int next = cur + dir[j];
				if (se.count(next)==0) {
					q.push(next);
					se.insert(next);
					result += dis;
					if (--k == 0) {
						return;
					}
				}
			}
		}
	}

}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		se.insert(a);
		q.push(a);
	}
	bfs();
	cout << result;
	return 0;
}

코드3(unordered_set)

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;


unordered_set<int> se;
int n, k;
int dir[2] = { 1,-1 };
queue<int> q;
long long result;
void bfs() {
	int dis = 0;
	while (!q.empty()) {
		int size = q.size();
		dis++;
		for (int i = 0; i < size; i++) {
			int cur = q.front();
			q.pop();

			for (int j = 0; j < 2; j++) {
				int next = cur + dir[j];
				if (se.count(next)==0) {
					q.push(next);
					se.insert(next);
					result += dis;
					if (--k == 0) {
						return;
					}
				}
			}
		}
	}

}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		se.insert(a);
		q.push(a);
	}
	bfs();
	cout << result;
	return 0;
}