[BOJ] 18513.샘터(BFS).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

샘터를 중심으로 주변으로 이동하며 집을 지어보면 빠르게 해를 구할 수 있다.

처음에는 조합인가 생각했었는데, 조합으로 하면 뻐어어엉 시간초과가 나버린다..

안타깝지만 당연한 결과다ㅠ

단, 또 생각해주어야 하는게

샘터가 -1억 ~ 1억 에 위치할 수 있어서

visited 처리도 고민을 해야한다.

boolean 배열 두 개를 만드는 방법도 있고,

0 ~ 100,000,000 을 체크하는 visited1

-1 ~ -100,000,000 을 체크하는 visited2 

boolean 배열 한 개를 만드는 방법도 있고,

0 ~ 200,000,000 을 체크하는 visited

단, visited 배열을 사용할 때, + 100,000,000 을 계속 해주어야 제대로 접근할 수 있다.

다음 HashSet을 사용하는 방법,

visited 배열을 사용하면 메모리 낭비가 있어서,

저장 공간이 유동적이고 빠른 탐색 속도를 보이는 HashSet 을 사용하는 방법이다.

#. Code_HashSet

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
 
public class BOJ18513 {
 
    static int N, K, MAX = 100000000;
    static int[] dx = { -1, 1 };
    static Set<Integer> visited;
 
    static class State {
        int x;
        int dist;
 
        public State(int x, int dist) {
            this.x = x;
            this.dist = dist;
        }
    }
 
    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()); // 샘터
        K = Integer.parseInt(st.nextToken()); // 지을 집
        visited = new HashSet<>();
 
        // 샘터 위치를 먼저 queue에 넣어주자.
        Queue<State> q = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            q.add(new State(tmp, 0));
            visited.add(tmp);
        }
        // 샘터를 중심으로 집을 지어보자.
        System.out.println(bfs(q));
    }
 
    private static long bfs(Queue<State> q) {
        long res = 0;
        int homeCnt = 0;
        
        out:while(!q.isEmpty()) {
            // 현재 좌표
            State now = q.poll();
            // 주변 땅을 봐볼까?
            for (int d = 0; d < 2; d++) {
                int xx = now.x + dx[d];
                // 범위를 벗어날 경우 pass
                if(xx < -MAX || xx > MAX) continue;
                // 이미 집을 지은 곳이라면 pass
                if(visited.contains(xx)) continue;
 
                // 여기에 집을 지어보자
                homeCnt++;
                res += now.dist + 1;
                // 집을 다 지었으면 
                if(homeCnt == K) break out;
                
                visited.add(xx);
                q.add(new State(xx, now.dist + 1));
            }
        }
        
        return res;
    }
 
}

#. Code_booleanArray

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    static int N, K, MAX = 100000000;
    static long res;
    static int[] dx = { -1, 1 };
    static boolean[] visitedUp, visitedDown;
 
    static class State implements Comparable<State> {
        int x;
        int dist;
 
        public State(int x, int dist) {
            this.x = x;
            this.dist = dist;
        }
 
        @Override
        public int compareTo(State o) {
            // TODO Auto-generated method stub
            return Integer.compare(this.dist, o.dist);
        }
    }
 
    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()); // 샘터
        K = Integer.parseInt(st.nextToken()); // 지을 집
        visitedUp = new boolean[100000000];
        visitedDown = new boolean[100000000];
 
        // 샘터 위치를 먼저 queue에 넣어주자.
        PriorityQueue<State> q = new PriorityQueue<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int tmp = Integer.parseInt(st.nextToken());
            q.add(new State(tmp, 0));
            if(tmp < 0) visitedDown[tmp * -1] = true;
            else visitedUp[tmp] = true;
        }
 
        bfs(q);
 
        System.out.println(res);
    }
 
    private static void bfs(Queue<State> q) {
        
        int homeCnt = 0;
        while(!q.isEmpty()) {
            State now = q.poll();
            
            for (int d = 0; d < 2; d++) {
                int xx = now.x + dx[d];
                // 범위를 벗어날 경우 pass
                if(xx <= -MAX || xx >= MAX) continue;
                // 이미 집을 지은 곳이라면 pass
                if(xx < 0) {
                    if(visitedDown[xx * -1]) continue;
                } else {
                    if(visitedUp[xx]) continue;
                }
 
                // 여기에 집을 지어보자
                homeCnt++;
                res += now.dist + 1;
                // 집을 다 지었으면 
                if(homeCnt == K) return;
                
                if(xx < 0) visitedDown[xx * -1] = true;
                else visitedUp[xx] = true;
                
                q.add(new State(xx, now.dist + 1));
            }
        }
        
    }
 
}