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

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

18513번: 샘터

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321; 

int N, K;
queue<int>q;
set<int>s; //방문체크용 (음수범위까지)
int dx[]={1, -1}; //좌우탐색

ll bfs()
{
    ll badluck = 1, result = 0; //불행도 기본 1, 합 기본 0
    while(!q.empty())
    {
        int size = q.size(); //q사이즈 고정 (변동)
        for(int i=0; i<size; i++) //쉼터 갯수만큼
        {
            int x = q.front(); q.pop();
            for(int j=0; j<2; j++) //좌우 탐색
            {
                int nx = x + dx[j];
                if(s.count(nx)) continue; //방문체크
                s.insert(nx); //방문처리
                q.push(nx); 
                result+=badluck; //불행저장
                if(!--K) return result; //집을 다 설치하면 종료
            }
        }
        badluck++; //불행수치 증가 (거리증가)
    }
    return result;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> K;
    for(int i=0; i<N; i++) 
    {
        int n;
        cin >> n;
        q.push(n);
        s.insert(n);
    }
    cout << bfs();
    return 0;
}

 

불행수치의 합이 가장 적으려면, 샘터와 가장 가깝게 집을 지어주면 된다.

따라서 bfs를 통해 현재 샘터를 기준으로 바로 옆에 하나씩 집을 추가해주며 불행수치를 추가해주면 된다.

 

샘터의 갯수가 여러개 이므로 bfs를 통해 탐색할때 q의 갯수만큼 반복하여 탐색하게 된다. (기준점이 여러가지)

q의 사이즈가 변동되므로 미리 size를 선언해주고 이를 사용하도록 해준다.

좌우로만 이동하므로, 이동 범위 배열은 {1, -1}로 선언하고 이에 맞게 이동한다. 

해당문제에서 방문체크를 위해 기존에 주로 사용하던 bool visited 배열로 체크하는 것이 아니라 set을 사용하였다.

이는 샘터의 위치가 음수인 케이스가 존재하여, 배열로는 음수 위치 지정이 불가능 하기 때문이다.

 

무사히 다음 값이 가능하다면 현재 불행수치를 합에 더해주고, 집을 설치했다는 것이므로 집의 갯수인 K를 하나 감소시킨다.

이렇게 감소시킨 K가 0이 된다면 모두 설치했다는 것이므로 바로 저장된 합을 반환하여 종료시킨다.

쉼터 갯수만큼 위 과정이 종료되면 불행수치가 증가하게 된다.

현 쉼터 위치 기준으로 바로 좌우값 탐색이 끝났고, 다음 값들은 그다음 위치이므로 거리가 1 증가하게 되는 것이다.

 

샘터의 값이 매우 크므로 이에 대한 불행수치 (거리수치) 도 매우 크다.

따라서 이에 관한 값인 badluck, result, 함수 bfs를 longlong으로 선언해주어야 한다.