Boj 32069 c++ 가로등

입력 범위가 10^18까지이기 때문에 배열 대신 맵을 사용해야 한다. 나는 unordered_map을 이용하여 풀이하였다.

어두운 정도를 낮은 것 부터 출력하는 것이기 때문에 dist를 사용하여 작은 것 부터 k개 만큼 출력하면 된다.

dist와 visited는 맵으로 변경하였다.

#include<iostream>
#include<unordered_map>
#include<queue>
typedef long long ll;
using namespace std;
unordered_map<ll, bool> visited;
unordered_map<ll, ll> dist;
queue<ll> q;
ll l, n, k, lmp;
void BFS(){
    ll cnt=0;
    while(!q.empty()){
        ll U=q.front(); q.pop();
        cout<<dist[U]<<"\n"; cnt++;
        if(cnt==k)return;
        ll nx1=U+1, nx2=U-1;
        if(!visited[nx1]&&nx1<=l){
            q.push(nx1);
            visited[nx1]=true;
            dist[nx1]=dist[U]+1;
        }
        if(!visited[nx2]&&nx2>=0){
            q.push(nx2);
            visited[nx2]=true;
            dist[nx2]=dist[U]+1;
        }
    }
}
int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin>>l>>n>>k;
    for(int i=0; i<n; i++){
        cin>>lmp;
        q.push(lmp);
        dist[lmp]=0; visited[lmp]=true;
    }
    BFS();
}