[백준] 18513번 샘터 (C++)

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

 

 

N개의 샘터와 M개의 집을 세우려고 할때 불행도의 합을 최소로 해야 한다.

 

불행도는 세우려는 집의 위치를 기준으로 가장 가까운 샘터의 위치의 차이의 합이다.

 

따라서 이를 해결하기 위해서 샘터 개수(N) 만큼 순회하며 샘터 위치를 기준으로 좌우로 배치하며 크기를 최소화 하는 방법을 생각하여

 

bfs + set을 사용하였다.

 

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct halloween {
    int cnt;
    int score;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
// int dx[] = {0, 0, 1, -1};
// int dy[] = {1, -1, 0, 0};
int dx[] = {-1, 1};
int N, K;
ll answer;
queue<pii> q;
set<int> st;

void bfs() {
    while(!q.empty()) {
        int x = q.front().first;
        int bad = q.front().second;
        q.pop();

        for(int i = 0; i < 2; i++) {
            int nx = x + dx[i];

            if(st.count(nx) == 0) {
                q.push({nx, bad+1});
                answer += bad + 1;
                K--;
                st.insert(nx);
            }

            if(!K) {
                cout << answer;
                return;
            }
        }
    }
}

void solve() {
    bfs();
}

void input() {
    cin >> N >> K;

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}