[백준 32069번] 가로등

문제 링크

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

 

문제 요약

수직선 도로 위해 \(N\) 개의 가로등이 위치해 있다. 각 위치에서 가장 가까운 가로등까지의 거리를 계산하고, 그 거리들을 오름차순으로 정렬한 뒤 앞에서부터 \(K\) 개 출력하는 문제이다.

 

문제 풀이

문제에서는 어두운 정도를 각 위치로부터 가장 가까운 가로등까지의 거리로 정의하고 있다. 그래서 처음에는 각 위치별로 가장 가까운 가로등까지의 거리를 모두 계산해야 한다고 생각할 수 있다. 하지만 도로의 길이 \(L\)이 최대 \(10^{18}\)까지 될 수 있기 때문에, 모든 위치를 전부 탐색하는 완전탐색은 사실상 불가능하다.

 

이 문제를 해결하기 위해서는 가로등을 기준으로 생각할 필요가 있다. 각 가로등들을 중심으로 가까운 위치들을 하나씩 방문해 나가면서 어두운 정도를 계산한다면, 모든 위치를 탐색하지 않고도 가로등으로부터 가장 가까운 \(K\) 개의 위치를 탐색과 동시에 알 수 있다.

 

이 아이디어를 구현하기 위해서는 BFS(너비 우선 탐색)이 적합하다. 일반적인 BFS에서는 시작 지점을 하나만 두고 탐색을 시작하지만, 이 문제에서는 여러 개의 가로등이 있으므로 큐에 모든 가로등의 위치를 넣고 시작한다. 또한, 방문한 지점을 저장하기 위해 배열을 사용할 수 도 있지만, 도로의 길이가 매우 길 수 있기 때문에 메모리를 생각해 set과 같은 자료구조를 사용할 수 있다.

 

소스 코드

#include <stdio.h>
#include <queue>
#include <set>

using namespace std;

long long l, a;
int n, k;
const long long dx[] = {-1, 1}; // 왼쪽과 오른쪽으로 이동하기 위한 배열
queue<pair<long long, long long>> q; // BFS를 위한 큐, (위치, 거리)
set<long long> visited; // 방문한 위치를 저장하는 집합

// 위치가 도로 범위 내에 있는지 확인하는 함수
bool isPossible(long long x) {
    return 0 <= x && x <= l;
}

int main() {
    // 도로 길이, 가로등 개수, 출력할 위치 개수를 입력 받는다
    scanf("%lld%d%d", &l, &n, &k);
    
    // 각 가로등의 위치를 입력 받고 큐에 추가, 방문 표시
    for (int i = 0 ; i < n ; ++i) {
        scanf("%lld", &a);
        q.push({ a, 0 });
        visited.insert(a);
    }
    
    // BFS 시작
    while (!q.empty()) {
        long long here = q.front().first;
        long long dist = q.front().second;
        q.pop();
        
        // 현재 위치의 어두운 정도 (가장 가까운 가로등까지의 거리)를 출력
        printf("%lld\n", dist);
        --k;
        
        // K개의 위치를 모두 출력했으면 프로그램 종료
        if (k == 0) {
            return 0;
        }
        
        // 현재 위치의 왼쪽과 오른쪽 이웃을 탐색
        for (int i = 0 ; i < 2 ; ++i) {
            long long there = here + dx[i];
            
            // 이웃 위치가 도로 범위 내에 있고 아직 방문하지 않았다면 큐에 추가
            if (isPossible(there) && !visited.count(there)) {
                q.push({ there, dist + 1 });
                visited.insert(there);
            }
        }
    }
}