[BOJ - JAVA] 18513 - 샘터 (BFS, 그래프)

# 주소

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

18513번: 샘터

# 문제

# 문제 해설 및 코드 리뷰

import java.util.*;
class Direction{
    int x;
    int dist;
    Direction(int x, int dist){
        this.x = x;
        this.dist = dist;
    }
}
class Main{
    static int n,m;
    static int[] dx = {-1,1};
    static HashSet<Integer> hash;
    static Queue<Direction> queue = new LinkedList<>();
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        hash = new HashSet<>();
        for(int i = 0; i < n; i++){
            int x = scan.nextInt();
            queue.offer(new Direction(x, 0));
            hash.add(x);
        }
        System.out.println(bfs());
    }
    static long bfs(){
        long sum = 0;
        int index = 0;
        out:while(!queue.isEmpty()){
            Direction now = queue.poll();
            for(int i = 0; i < 2; i++){
                int nx = now.x + dx[i];
                if(nx < -1000000000 || nx > 1000000000)
                    continue;
                if(hash.contains(nx))
                    continue;
                index++;
                sum += now.dist + 1;
                if(index == m)
                    break out;
                hash.add(nx);
                queue.offer(new Direction(nx,now.dist + 1));
            }
        }
        return sum;
    }
}

visit배열을 사용하기엔 인덱스가 -10억 부터 10억까지라 연산이 굉장히 많아질 것 같습니다.

또 일일히 모든 배열을 만들어서 한다 생각하니 눈앞이 깜깜하군요...

관점을 조금 바꾸어서, Queue와 HashSet을 이용하여 풀이를 해보려고 합니다.

Queue는 n개의 점을 모두 담아서 좌표와 거리를 모두 담아서 각 점마다의 근처 인덱스에 집을 설치하여 거리를 구할 것이구요.

hash에는 n개의 점을 모두 담되 좌표값만 등록을 할 것입니다.

만약 hash에 중복된 점이 있다면 집을 설치하면 안되므로 탐색에 용이한 HashSet을 사용합니다.

 

따라서 Queue는 평상시 DFS, BFS방식으로 풀 때의 arr[]배열의 역할과 비슷하다고 볼 수 있습니다.

그리고 hash는 visit[]배열과 비슷한 모습을 보입니다. 

이 점 유념하시면 좋겠습니다.

이제 풀이를 해보겠습니다.

static int n,m;
static int[] dx = {-1,1};
static HashSet<Integer> hash;
static Queue<Direction> queue = new LinkedList<>();
public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    n = scan.nextInt();
    m = scan.nextInt();
    hash = new HashSet<>();
    for(int i = 0; i < n; i++){
        int x = scan.nextInt();
        queue.offer(new Direction(x, 0));
        hash.add(x);
    }

dx의 이동방향은 좌, 우로만 결정지을 수 있습니다.

수직선이기 때문에 그렇겠죠?

따라서 각 점에 대해 2번의 for문을 loop할 수 있겠습니다.

또한 HashSet과 Queue를 static에서 선언하고 넘어갈 것이고 Buffer로 입력 받는 것이 맞지만 Scanner로 풀었습니다.

(가독성은 아무리 뭐라해도 Scanner를 못이기더라구요)

n번의 for문을 시행하여 x를 입력받고 queue에는 (x, 0)을, hash에는 x를 삽입합니다.

이 때 queue의 0은 각 점에서의 거리를 뜻합니다.

당연히 x점에서 x까지의 거리는 0이므로 초기값은 0이 되어야합니다.

bfs내부를 살펴보겠습니다.

long sum = 0;
int index = 0;
out:while(!queue.isEmpty()){
    Direction now = queue.poll();
    for(int i = 0; i < 2; i++){
        int nx = now.x + dx[i];
        if(nx < -1000000000 || nx > 1000000000)
            continue;
        if(hash.contains(nx))
            continue;
        index++;
        sum += now.dist + 1;
        if(index == m)
            break out;
        hash.add(nx);
        queue.offer(new Direction(nx,now.dist + 1));
    }
}
return sum;

sum에는 최소가 될 값의 총 합을 의미합니다.

index는 횟수를 의미하는데, 이것이 m번 연산하게 되면 while문을 종료할 것입니다.

그런데 while문안에 또 for문이 있으니, 단순히 break만 해서는 밖으로 나올 수가 없겠죠?

따라서 out:while, break-out; 문을 써서 break지점을 설정할 수 있습니다.

out말고도 다른 문자로도 가능하니 참고부탁드립니다.

for문은 2번 돌릴건데, nx는 +1또는 -1만큼 이동한 점이 될테고 만약 이 nx가 -10억이나 10억보다 크다면 continue;하게 됩니다.

또한 hash에 nx가 있다면 (방문한 점이거나 설치된 인덱스라면) 이것도 continue합니다.

이후 앞선 상황의 이외의 경우에 index++하고 sum에는 now.dix + 1을 하게됩니다.

만약 처음 queue에 담았던 인덱스 근처에 완전한 빈공간이 있다면 당연히 sum에는 1을 추가하겠지요.

하지만 그렇지 않을 경우 (hash에 값이 있을 경우)엔 해당 로직까지 진행되지 않을 것입니다.

따라서 전혀 방문하지 않은 인덱스일 경우엔 hash에 값을 담고 queue에도 nx와 현재 점 + 1한 것을 담아야 하며 방문한 인덱스는 continue해주는 것입니다.

모두 끝나면 break out해서 빠져나온 뒤 sum을 return하여 주시면 되겠습니다.

감사합니다.