샘터

📍 문제 설명

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

18513번: 샘터

 

💡 접근

배열이 아닌 Set을 이용해서 좌표 방문 여부를 체크해줬는데 계속 메모리 초과가 났었다.

위의 문제는 집을 모두 지었을 때의 체크를 루프 바깥에서 해줬기 때문이다.

그리고 바깥에서 체크를 해주면 루프 안에서 집이 하나 더 만들어질 수도 있기 때문에 오답이다.

타 블로그를 참고해서 새롭게 알게된 문법이 있다.

out:while 문법을 쓰고 안에서 break out;을 사용하면 while 문을 바로 빠져나온다.

 

그리고나서도 계속 틀렸습니다.가 떴는데, 샘터의 위치는 -1억~1억이지만 집의 좌표는 정해져 있지 않기 때문에 범위를 설정해놓지 않아야한다.

 

👩‍💻 코드

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

public class Main {
    static int[] arr = {-1,1};
    static int n, m, max = 100000000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); //샘터 갯수
        m = Integer.parseInt(st.nextToken()); //지을 집 갯수

        st = new StringTokenizer(br.readLine());
        Queue<Point> q = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken()); //집 위치
            q.add(new Point(x, 0));
            set.add(x);
        }

        int cnt = 0;
        long result = 0;

        out:while (!q.isEmpty()) {
            Point cp = q.poll();
            for(int i = 0; i < 2; i++) {
                int nx = cp.x + arr[i];

                if(set.contains(nx)) continue;
                result += cp.distance+1;
                cnt++;
                set.add(nx);
                if(cnt == m) break out;
                q.offer(new Point(nx, cp.distance+1));
            }
        }
        System.out.println(result);

    }

    private static class Point {
        private int x;
        private int distance;

        public Point(int x, int distance) {
            this.x = x;
            this.distance = distance;
        }

        @Override
        public String toString() {
            return "Point{" +
                    "x=" + x +
                    ", distance=" + distance +
                    '}';
        }
    }
}