문제 이해 단계
https://www.acmicpc.net/problem/18513
문제 이해 자체는 그렇게 어렵지 않은 문제.
N개의 샘터와 K개의 집이 주어진다.
이후 샘터의 위치가 지정되고 집의 위치를 지정하는데
집이 샘터에 멀어질수록 불행도가 올라간다.
이때, 불행도의 합을 최소화할 수 있도록 집을 배치한 후,
그때의 합의 최솟값을 구하는 문제이다.
샘터에는 집을 지을 수 없고, 집을 겹쳐지을 수도 없다.
문제 접근 단계
불행도를 최소화하기 위해서는 샘터에 양옆에 차곡차곡 최대한 붙여서 짓는 것이 가장 좋다/
N개의 샘터가 있다면, N개의 샘터를 하나씩 돌아가면서 양쪽에 집을 두면서 진행하는 것이 좋다.
이런 동작원리가 BFS와 흡사하다고 생각하여 BFS로 접근하기로 했다.
1. 모든 샘터들을 큐에 넣는다.
2. 샘터 양쪽을 확인한 후 집이나 샘터가 없다면 +1을 더한다.
3. 남은 집의 개수를 하나 빼준다.
4. 2~3을 남은 집의 개수가 0개가 될 때까지 반복한다.
위 방식으로 BFS를 구현하면 된다고 생각했다.
근데 샘터의 범위가 -1억에서 1억으로 총 2억으로 너무 크고
음수까지 포함되어 있어 배열을 사용하지 못한다.
그리고 억지로 쓸려고 하면 메모리초과가 뜰 게 뻔하다.
그래서 Set을 사용하기로 했다. 이왕이면 좀 더 빠르면 unorderd_set을 사용했다.
unordered_set을 활용하면 음수를 인덱스로 활용하여 방문처리를 할 수 있어서 편리하다.
문제 구현 단계
long long Bfs(int count) {
long long sum = 0;
long long dist = 1;
while (!q.empty()) {
int size = q.size();
while (size--) {
int x = q.front();
q.pop();
for (int i = 0; i < 2; i++) {
int nx = x + dx[i];
if (!(s.count(nx) >= 1)) {
q.push(nx);
sum += dist;
s.insert(nx);
count--;
if (count == 0) return sum;
}
}
}
dist++;
}
return sum;
}접근 단계에서 세웠던 방식을 구현한 BFS 함수이다.
long long 형으로 선언한 이유는 샘터의 위치가 -1억~1억이고,
샘터의 개수가 최대 100,000개 이기 때문에 자칫하면 엄청나게 큰 합이 나올 수 있다.
그래서 오버플로우를 방지하기 위해 long long을 사용하였다.
매개변수로는 K 즉, 집의 개수를 받는다.
그리고 반환할 값인 sum과 샘터와의 거리 dist를 1로 초기화해 주고
새로운 층(예를 들어, 가장 가깝던 양쪽에서 그다음으로 가까운 양쪽으로 위치 지정할 때) 때 dist를 1씩 더해준다.
여기서는 unordered_set을 사용하였기 때문에, 큐에서 뺄 때마다 방문을 확인하여 insert를 해준다.
그리고 s.count(해당 자리) >= 1로 방문을 했는지 안 했는지를 확인한다.
(1: 방문 O 0 : 방문 X)
큐에 새로운 값을 넣는다는 하나의 집을 위치시킨다는 뜻이므로 count를 하나 빼준다.
이러한 행위를 count == 0 일 때까지 반복하고 sum을 반환하여 함수를 끝낸다.
핵심 코드는 위가 끝이다.
밑에는 전체 코드를 올리고 끝내겠다.
#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;
int N, K;
int dx[] = { -1,1 };
queue<int> q;
unordered_set<int> s;
long long Bfs(int count) {
long long sum = 0;
long long dist = 1;
while (!q.empty()) {
int size = q.size();
while (size--) {
int x = q.front();
q.pop();
for (int i = 0; i < 2; i++) {
int nx = x + dx[i];
if (!(s.count(nx) >= 1)) {
q.push(nx);
sum += dist;
s.insert(nx);
count--;
if (count == 0) return sum;
}
}
}
dist++;
}
return sum;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin >> N >> K;
for (int i = 1; i <= N; i++) {
int v;
cin >> v;
q.push(v);
s.insert(v);
}
long long ans = Bfs(K);
cout << ans;
}
시행착오
위 문제에 접근하여 구현하는 것은 생각보다 간단하였지만, 메모리 초과를 피할 수가 없었다.
왜냐하면 값이 음수가 포함되고 -1억에서 1억이라는 엄청나게 큰 범위가 포함되어 있었기 때문이다.
그래서 배열을 사용하여 방문을 확인할 수 없었고,
억지로 양수로 변환했다 하더라도 2억이기 때문에 메모리초과가 떠서 풀 수가 없었다.
그래서 이것저것 알아보니 Set을 이용하여 방문처리를 하는 방식을 새로 배웠다.
이때까지는 배열이나 벡터만을 사용하여 방문처리를 해온 나에게는
새로운 접근이었고 Set을 사용해 본 첫 문제였다고 할 수 있다.
정말 신선했고, 또 문제를 바라보는 식견이 넓어진 기분이었다.
나에게는 정말 좋은 문제였던 것 같다. 여태껏 풀어보지 못했던 BFS 문제였다.