문제
일직선 상의 공간에 N개의 샘터가 존재하며, K채의 집을 짓고자 한다. 모든 샘터 및 집이 존재하는 위치는 항상 정수 형태이다. 이때 일직선 상의 공간에서 N개의 샘터 및 K채의 집들은 모두 서로 다른 위치에 존재한다. 다시 말해 하나의 위치에는 샘터가 있거나, 집이 있거나, 혹은 아무것도 없다.
K채의 집을 지을 때, 가능하면 샘터의 주변에 집들을 지어서 K채의 모든 집에 대한 불행도의 합이 최소가 되도록 짓고자 한다. 이때 특정한 집에 대한 불행도란, 가장 가까운 샘터까지의 거리(Distance)로 정의된다. 예를 들어 특정한 집이 1에 위치하고, 그 집과 가장 가까운 샘터가 -5에 위치한다고 하면, 이 집의 불행도는 6이다.
N=2, K=5일 때, 모든 집에 대한 불행도의 합이 최소가 되도록 집을 짓는 경우를 고려해보자. 아래 그림과 같이 두 개의 샘터가 0, 3의 위치에 존재한다고 가정하자.
이때 다음과 같이 5채의 집을 설치하면, 각 집의 불행도의 합이 2+1+1+1+1=6로 최소가 된다. 집을 짓는 가능한 경우의 수는 여러 가지가 될 수 있지만, 불행도의 합을 6보다 작게 만드는 방법은 없다.
입력
첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 <= N, K <= 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 <= 샘터의 위치 <= 100,000,000) 단, 모든 N개의 샘터의 위치들은 서로 다르게 주어진다.
출력
첫째 줄에 모든 집에 대한 불행도의 합의 최솟값을 출력한다.
풀이
모든 샘터를 동시에 시작점으로 두는 멀티 소스 BFS가 정답이다. 샘터에서 거리 1인 칸들, 거리 2인 칸들 순서로 확장하면 가장 가까운 집 후보부터 자연스럽게 채우게 된다.
코드에서는 모든 샘터를 큐에 넣고, 방문한 위치는 Set으로 관리한다. BFS로 양옆 한 칸씩 확장하면서 처음 방문한 빈 칸을 집으로 선택하고, 그 거리만큼 불행도를 더한다. 이렇게 K개를 채우는 순간 종료하면 된다.
코드에서는 모든 샘터를 처음부터 큐에 넣고, 이미 샘터가 있는 위치도 visited에 표시해 둔다. 그러면 BFS가 한 겹씩 퍼질 때마다 "가장 가까운 아직 비어 있는 위치"들이 차례대로 나온다. 각 위치는 처음 방문한 순간이 가장 가까운 샘터와의 거리이므로, 그 값을 그대로 불행도에 더하면 된다.
위치는 음수까지 내려갈 수 있어서 배열 대신 HashSet으로 방문 여부를 관리한 점도 중요하다. 좌우로만 확장하면 되므로 매 상태에서 다음 후보는 x - 1, x + 1 두 개뿐이고, 집을 K개 지은 순간 바로 종료하면 불필요한 탐색도 줄일 수 있다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[] arr = new int[N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(st.nextToken());
System.out.println(solve(N, K, arr));
}
static long solve(int N, int K, int[] arr) {
long ans = 0;
int cnt = 1;
Queue<int[]> q = new ArrayDeque<>();
Set<Integer> visited = new HashSet<>();
for (int n : arr) {
visited.add(n);
q.offer(new int[]{n, 0});
}
while (!q.isEmpty() && K > 0) {
int[] cur = q.poll();
int loc = cur[0];
int dis = cur[1];
int[] dx = {-1, 1};
for (int dir : dx) {
int next = loc + dir;
if (!visited.contains(next)) {
q.offer(new int[]{next, dis + 1});
visited.add(next);
ans += (dis + 1);
K--;
}
if (K == 0) break;
}
}
return ans;
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
가장 가까운 자리부터 채워야 하는 문제라서 BFS와 궁합이 아주 좋다. 여러 샘터를 한 번에 시작하는 순간 정답 구조가 바로 나온다.
