백준 18513 샘터

1. 문제

문제링크

2. 접근법

• 문제 접근
  • 집은 샘터기준으로 1, -1씩 떨어져 있는 경우가 제일 가까운 경우이므로 {-1, 1}을 디폴트로 집이 위치해야 할 거리를 잡아준다.
  • 최단거리를 구하는 문제이므로 BFS알고리즘을 사용한다.
  • 집을 지은 곳에는 방문체크를 해야하므로 set을 사용했다. set이나 unordered_set이나 위 문제에서는 상관없기 때문에 속도가 빠른 unordered_set을 사용하였다.
  • 집과 샘터의 거리를 구하기 위해 처음 샘터의 좌표를 입력받으면 Q에 값을 넣고 BFS함수에서 Q의 사이즈만큼 while문을 한번 더 돌린다. -> 거리가 짧을수록 불행도의 합이 최소가 되므로 while문이 한번 끝날때마다 거리+1로 갱신해준다.

3. 코드

#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#include <unordered_set>	//unordered_set이 일반 set보다 속도가 빠름

using namespace std;

typedef long long ll;
int N, K;	
int dx[2] = { 1, -1 };
queue<int> Q;
unordered_set<int> s;

ll BFS()
{
	ll ans = 0, dis = 1;

	while (!Q.empty())
	{
		int size = Q.size();
		while (size--)
		{
			int housePos = Q.front();
			Q.pop();

			for (int i = 0; i < 2; i++)
			{
				int pos = housePos + dx[i];
				if (!(s.count(pos) >= 1))
				{

					K--;
					ans += dis;
					s.insert(pos);
					Q.push(pos);

					if (K == 0)
						return ans;
				}
			}
		}
		dis++;
	}
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		Q.push(a);
		s.insert(a);
	}
	cout << BFS() << "\n";
	return 0;
}

4. 시간복잡도

BFS알고리즘을 사용하는 문제이며, 인접행렬을 이용하였다.
여기서 각 정점에서 연결된 간선이 2개(1, -1)씩이므로 총 개수는 O(2NK)인데 상수배는 무시할 수 있다. 또한 BFS탐색과정에서 정점을 O(NK)개 보고 간선도 O(NK)개 보니 O(NK+NK)=O(2NK)인데 상수배는 무시하므로, 시간복잡도는 O(NK)가 된다.

5. 결과