18513번 샘터

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

boj 백준 샘터 18513 bfs 복습 실수 필수 long 자료형

그림을 잘 보면, 샘터를 기준으로 양 옆으로 하나 씩 집을 설치하면 되는 것을 알 수 있다.

이를 통해, 샘터를 기준으로 방문 처리를 하면서 1 씩 퍼져나가는 것으로 볼 때

필요한 알고리즘은 bfs임을 알 수 있다.

틀렸습니다를 받았길래 알고보니, 정답 범위가 long long이었다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n, k;
int d[2] = { 1, -1 };
queue<pair<int, int> > q;
set<int> s;
 
long long bfs()
{
    long long ret = 0;
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int x = q.front().first;
            int p = q.front().second;
 
            q.pop();
 
            for (int i = 0; i < 2; i++) {
                int nx = x + d[i];
 
                if (nx < -100000000 || nx > 100000000 || s.count(nx) >= 1) {
                    continue;
                }
 
                --k;
                ret += abs(nx - p);
 
                if (k == 0) {
                    return ret;
                }
 
                s.insert(nx);
                q.push({ nx, p });
            }
        }
    }
 
    return ret;
}
 
int main()
{
    cin.tie(0);
    scanf("%d %d", &n, &k);
 
    int input;
    for (int i = 0; i < n; i++) {
        scanf("%d", &input);
        q.push({ input, input });
        s.insert(input);
    }
 
    printf("%lld\n", bfs());
 
    return 0;
}