[백준] 18513 - 샘터

https://www.acmicpc.net/problem/18513

18513번: 샘터

 

처음에는 단순히 그리디 하게 접근해 배열의 인덱스를 이용한 좌표 저장을 하려고 했다.

하지만 샘터의 위치는 최대 2억 1개가 올 수 있고, 집의 위치는 그보다 더한 곳에 지어질 수 있다고 생각해 그만두었다.

 

그래서 bfs를 통해 탐색하였다.

다음과 같은 큐를 생성하였다.

 

// 샘터의 위치, 현재 위치
queue<pair<int, int>> q;

 

샘터의 위치는 항상 고정이고, bfs는 최단 거리를 탐색하므로 항상 |현재 위치 - 샘터의 위치| 만큼의 불행도가 더해진다는 것을 알 수 있다.

 

참고로 방문 체크는 set, unordered_set 둘 중 아무거나 사용해도 된다.

 

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

int n, k;
set<long long> visit;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k;

	queue<pair<long long, long long>> q; //샘터의 위치, 현재 위치

	for (int i = 0; i < n; i++) {
		long long a;
		cin >> a;
		q.push({ a,a });
		visit.insert(a);
	}

	long long ans = 0;

	while (!q.empty() && k) {
		long long a = q.front().first;
		long long b = q.front().second;
		q.pop();

		if (a != b) {
			ans += abs(a - b);
			k--;
		}

		if (k == 0)break;

		if (!visit.count(b - 1)) {
			visit.insert(b - 1);
			q.push({ a,b - 1 });
		}
		if (!visit.count(b + 1)) {
			visit.insert(b + 1);
			q.push({ a,b + 1 });
		}
	}

	cout << ans;
}