백준 18513번 : 샘터

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

18513번: 샘터

 

 

 

 

 

문제

• 일직선 상의 공간에 N개의 샘터가 존재하며, K채의 집을 짓고자 한다. 모든 샘터 및 집이 존재하는 위치는 항상 정수 형태이다.
• 이때 일직선 상의 공간에서 N개의 샘터 및 K채의 집들은 모두 서로 다른 위치에 존재한다.
• K채의 집을 지을 때, 가능하면 샘터의 주변에 집들을 지어서 K채의 모든 집에 대한 불행도의 합이 최소가 되도록 짓고자 한다.
• 불행도란, 가장 가까운 샘터까지의 거리(Distance)로 정의된다.
• 모든 집에 대한 불행도의 합의 최솟값을 출력한다.

 

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

 

 

제한사항

• 1 ≤ N, K ≤ 100,000
• 100,000,000 ≤ 샘터의 위치 ≤ 100,000,000

 

 

 

 

 

풀이

• BFS 탐색

 불행도의 합이 최소가 되려면, 집들을 최대한 샘터에 가깝게 지어야 한다. 샘터를 기준으로 +1씩 거리가 멀어지므로, 모든 샘터에 대해 +1씩 집의 위치를 움직이며 집을 지어주면 된다. 

 

 큐에 모든 집의 좌표를 담고, 큐의 사이즈만큼 끊어서 탐색을 하도록 하면, 같은 거리 만큼 끊어서 탐색을 할 수 있고, 거리의 합인 불행도를 같이 계산할 수 있다.

 

 

• 샘터과 집이 있는지 여부 저장 : Set

 모든 샘터와 모든 집이 서로 다른 위치에 존재하므로, 탐색을 할 때마다 해당 위치에 샘터나 집이 있는지 확인을 해줘야 한다.

 

보통 그래프 탐색에서 visited라는 boolean형의 방문 배열을 만들어서 방문 체크 및 확인을 한다. 하지만, 이 문제에서는 샘터의 위치의 범위가  -100,000,000  ~ 100,000,000 으로, 이것을 배열로 옮겨 표현한다면 무려 약 2억만큼의 크기가 필요하다. 너무너무 큰 숫자이다.. 메모리 초과가 날 것이다!

 

 집과 샘터의 개수는 최대 10만으로, 방문 체크에 2억만큼을 다 쓰지 않을 것이다. 따라서 자료구조를 Set으로 바꿔 저장하고, 해당 위치에 있는지를 확인하도록 했다.

 

 

 

 

 

코드

package algorithm;

import java.io.*;
import java.util.*;

public class BOJ_샘터 {
	static int[] dx = {-1, 1};

	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(bfs(arr, K));
	}

	public static long bfs(int[] arr, int k) {
		Queue<Integer> queue = new LinkedList<>(); //탐색을 위한 큐
		HashSet<Integer> visited = new HashSet<>(); //집이 있는지 저장
		
		for(int water : arr) { //샘터 위치를 큐에 넣음
			queue.add(water);
			visited.add(water);
		}
		
		int house = 0; //지은 집의 개수
		long sum = 0; //불행도 합
		int dist = 1; //거리
		
		while(!queue.isEmpty()) {
			int size = queue.size();
			for(int s = 0; s < size; s++) { //거리별로 끊어서 탐색
				int x = queue.poll();
				
				for(int d = 0; d < 2; d++) {
					int nx = x + dx[d];
					
					if(!visited.contains(nx)) { //집이 없음
						queue.add(nx);
						visited.add(nx);
						house++;
						sum += dist;
						
						if(house == k) return sum; //k개 만큼 집 지음
					}
				}
			}
			dist++; //거리 증가
		}
		return sum;
	}

}

 

 

 

 

 

 

결과

 

위에 메모리 초과는 visited를 2억 개의 배열로 만들었을 경우로 시험삼아 돌려봤을 때인데 역시 터진다.

 

 

 

 

 

배운점

• 좌표 범위가 넓을 때는 배열 말고 자료구조를 쓰자