[자바] 백준 18513 - 샘터 (java)

목차

 

문제 : boj18513

 

 

필요 알고리즘 개념

• BFS (너비 우선 탐색)
  
  • BFS로 풀 수 있는 문제이다. 논리는 약간 그리디에 가까운 것 같다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

   샘터가 아래처럼 3개가 있다고 해보자. 당연하게도 샘터에서 가장 가까운 곳 부터 집을 두는 것이 이득일 것이다.

 

  따라서 각 샘터에서 출발해 좌우로 퍼지면서 집을 지어주면 된다. 거리가 1 떨어진 집은 아래와 같다. 거리가 1 떨어진 곳에 6채의 집을 지을 수 있다.

 

  이미 지어져서 더이상 퍼지지 못하는 곳은 가지 않는다. 그렇다면 거리가 2 떨어진 집은 아래와 같다. 3채의 집을 지을 수 있다. 이런식으로 좌우로 퍼져나가면서 거리를 1,2,3,.. 씩 늘리면서 지어주면 된다.

 

  가장 간단하게 위와 같이 동작할 수 있는 알고리즘은 BFS이므로 난 BFS를 사용했다. 

 

 

코드 : github

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        Queue<int[]> q = new ArrayDeque<>();
        st = new StringTokenizer(br.readLine());
        Set<Integer> v = new HashSet<>();
        while (n-->0) {
            int cur = Integer.parseInt(st.nextToken());
            v.add(cur);
            q.add(new int[]{cur, 0});
        }

        long sum = 0 ;
        while (k!=0 && !q.isEmpty()) {
            int[] cur = q.poll();
            int idx = cur[0];
            int dist = cur[1];
            if (!v.contains(idx-1)) {
                k--;
                v.add(idx-1);
                sum += dist+1;
                q.add(new int[] {idx-1, dist+1});
            }
            if (k==0) break;
            if (!v.contains(idx+1)) {
                k--;
                v.add(idx+1);
                sum += dist+1;
                q.add(new int[] {idx+1, dist+1});
            }
        }

        System.out.println(sum);
    }
}