[백준] 18513번 : 샘터 Gold4(골드4) - JAVA[자바]

[Gold IV] 샘터 - 18513

문제 링크

성능 요약

메모리: 57152 KB, 시간: 428 ms

분류

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

제출 일자

2024년 6월 19일 14:39:39

문제 설명

일직선 상의 공간에 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개의 샘터의 위치들은 서로 다르게 주어진다.

출력

첫째 줄에 모든 집에 대한 불행도의 합의 최솟값을 출력한다.

 

접근 방법

1. 각 샘터를 기준으로 BFS를 진행한다.

2. BFS는 시간순으로 방문하기에 먼저 방문한 위치가 있다면 더 방문해주지 않는다.

3. 방문 처리를 위해서 Set을 이용하면 더 간단하게 구현이 가능하다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * BOJ_18513_G4_샘터
 * 메모리: 57152KB
 * 시간: 428ms
 * 접근 방법
 * 1. 각 샘터를 기준으로 BFS를 돌려준다.
 * 2. BFS는 시간순으로 방문하기에 먼저 방문한 위치가 있다면 더 방문해주지 않는다.
 * 3. 방문 처리를 위해 Set을 이용하면 더 간단하게 구현 가능하다.
 */
public class BOJ_18513_샘터 {
    static class Point {
        int idx;
        int count;

        public Point(int idx, int count) {
            this.idx = idx;
            this.count = count;
        }
    }

    static Set<Integer> visit = new HashSet<>();
    static Queue<Point> queue = new LinkedList<>();

    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 M = Integer.parseInt(st.nextToken());

        // Input
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int idx = Integer.parseInt(st.nextToken());
            visit.add(idx);
            queue.add(new Point(idx, 0));
        }// Input End

        System.out.println(solve(M));
    }

    private static long solve(int count) {
        long answer = 0;

        int[] dir = {-1, 1};
        while (!queue.isEmpty()) {
            Point cur = queue.poll();

            for (int i = 0; i <= 1; i++) {
                int nX = cur.idx + dir[i];
                if(!visit.contains(nX)) {
                    queue.add(new Point(nX, cur.count + 1));
                    System.out.println(nX);
                    visit.add(nX);
                    count--;
                    answer += cur.count + 1;
                    if(count == 0) return answer;
                }
            }
        }

        return answer;
    }
}