백준(BOJ) 18513 샘터 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/18513

18513번: 샘터

문제 풀이에 이용된 알고리즘: bfs, (자료구조)set

 

집을 설치하는 다양한 경우의 수가 존재하므로 가장 먼저 떠올리는 것은 완전 탐색이었다. 하지만 탐색 범위가 너무 넓기 때문에 말이 되지 않고, 그렇다고 이진 탐색을 이용하기에도 적합하지 않았다.

 

가장 가까운 샘물까지의 거리를 1, 2, 3...으로 하나씩 증가시키며, 집을 설치할 수 있는 경우의 수들을 합산해가며 k개의 집을 설치할 수 있다면 중단하도록 하는 방식을 생각했다.

 

처음에는 샘물이 존재할 수 있는 범위와 집이 설치될 수 있는 범위가 동일하다고 생각하여, -1억~1억의 좌표를 0~2억의 범위를 갖는 배열로 다루려고 했으나, 집이 설치될 수 있는 범위에는 제한이 없음을 뒤늦게 알게 되었다.

 

하지만 어떤 지점이 샘물로부터 얼마나 떨어져있는지 파악하는 과정에서, 중복 처리가 발생할 수 있기 때문에 소위 말하는 visited 배열이 필요한 상황이었고 다음과 같이 문제를 풀었다.

 

1. 샘물들로부터 최대한 가까운 지점들에 집을 설치해나가야 하므로 bfs를 이용한다.

 

2. 범위가 제한되지 않아서 visited 배열을 도입할 수 없으므로, 어떤 점이 처리되었는 지를 "집합"을 이용하여 표현한다. 집이 설치되었거나, 샘물이 존재하는 지점을 집합 s에 저장하고, 어떤 점이 처리되었는 지는 count함수를 이용하여 확인한다.

 

3. 샘물로부터 떨어져있는 거리를 확인하며 bfs를 적용하기 위해, queue의 사이즈만큼 while문이 한 번 돌면 distance값을 변화시켜 나간다.(코드에서 확인 가능)

 

4. 샘물의 범위를 보아서는 해당 문제에 등장할 수 있는 자료의 범위가 고작 1억인 것 같지만 불행도는 굉장히 큰 값이 등장할 수 있다. 따라서 long long 자료형으로 최종적인 연산을 진행한다.

 

/* BOJ 18513 샘터 */
#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
#include <string.h>
#include <set>
#include <unordered_set>
 
#define endl '\n'
 
using namespace std;
 
typedef long long ll;
 
int n, k;
queue<int> q;
unordered_set<int> s;
int dx[] = { 1, -1 };
 
ll bfs()
{
    ll distance = 1, cnt = 0, ans = 0;
    while (!q.empty())
    {
        int q_size = q.size();
        while (q_size--)
        {
            int cur = q.front();
            q.pop();
 
            for (int i = 0; i < 2; i++)
            {
                int next = cur + dx[i];
                // 방문한적 없는
                //=집을 설치하지 않았거나, 샘물이 아닌 좌표인 경우
                if (!(s.count(next) >= 1))
                {
                    s.insert(next); // 방문처리하고
                    q.push(next); // 큐에 삽입
            
                    cnt++; // 설치한 집의 수 1 증가
                    ans += distance; // 불행도 계산 및 합산
 
                    if (cnt == k) // k개의 집을 모두 설치한 경우
                        return ans; // 총 불행도 반환
 
                }
            }
        }
        distance++; // 불행도 연산을 위한, 가장 가까운 샘물까지의 거리
    }
    return ans; 
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        q.push(a);
        s.insert(a); // 방문처리
    }
 
    ll ans = bfs();
 
    cout << ans << endl;
    
    return 0;
}