BOJ_18513_샘터 (Java)

[Gold IV] 샘터 - 18513

문제 링크

성능 요약

메모리: 56076 KB, 시간: 560 ms

분류

너비 우선 탐색, 자료 구조, 그래프 이론, 그래프 탐색

제출 일자

2025년 2월 4일 23:16:33

문제 설명

일직선 상의 공간에 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 문제다. 처음에 한참 삽질한 방법은 아직도 왜 틀린지 모르겠다. 그림과 같은 방법으로 풀었었는데 이 방법으로 모든 예제를 찾아보고 만들어서 테스트해봤는데 다 맞지만 틀려서 방법을 변경했다.

모든 샘물에서 bfs동시에 돌리면서 K개까지 탐색했다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

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

public class Main {
    class Node{
	int x;
	int cnt;
	public Node(int x, int cnt) {
		this.x = x;
		this.cnt = cnt;
	}
}
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, K;
    static int[] arr, dx = {-1, 1};
	static long res = 0;
    static Queue<Node> queue = new LinkedList<>();
	public static HashSet<Integer> visited = new HashSet<>();
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_18513_샘터/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
    	K = Integer.parseInt(st.nextToken());

    	arr = new int[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    	}

        for(int i=0;i<N;i++) {
    		queue.offer(new Node(arr[i], 0)); //BFS 시작위치
    		visited.add(arr[i]);
    	}

        bfs();

        bw.write(String.valueOf(res));
        bw.flush();
        bw.close();
        br.close();
    }

    private void bfs() {
        int houseCnt = 0;
        while(!queue.isEmpty()) {
            Node curr = queue.poll();
            int currX = curr.x;
            int currCnt = curr.cnt;
            res += currCnt;
            for(int k=0; k<2; k++) {
                int nx = currX + dx[k];
                if(visited.contains(nx)) continue;
                if(houseCnt >= K) continue;
                queue.offer(new Node(nx, currCnt+1));
                visited.add(nx);

                houseCnt++;
            }
        }
    }
}