본문 바로가기
PS/BOJ

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

by Nahwasa 2023. 3. 3.

목차

     

    문제 : 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);
        }
    }

    댓글