[백준, Java] 18513번, 샘터(그래프 탐색)

문제 링크

18513번: 샘터

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

 

접근 방법

이 문제에 핵심

 

1. N개의 샘터가 존재하고 K개의 집은 서로 다른 위치에 존재할 수 있습니다.

2. 집들의 불행도는 가장 가까운 샘터의 거리의 값입니다.

3. K개 집의 위치를 정할 수 있을 때, 불행도의 합이 최소가 되는 값을 결과로 출력해야 합니다.

4. 샘터는 -100,000,000 ~ 100,000,000 위치에 존재합니다.

 

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 샘터를 기준으로 그래프 탐색을 진행하여 최소가 되는 불행도의 합을 탐색합니다.

 

3. 탐색을 통해 얻은 불행도의 최소합을 결과로 출력합니다.

 

집 설치 여부 확인하기

 

샘터에 대해서 그래프 탐색하기 이전에 해당 위치에 집을 설치하였는지 여부를 알 수 있는 방법이 필요합니다.

 

샘터에 위치는 음수 값도 될 수 있기 때문에 boolean[]으로 정의하기 위해서 추가적인 방법이 필요합니다.

 

집의 개수가 최대 100,000개이기 때문에 가장 낮은 위치에 설치할 수 있는 집은 -100,050,000입니다.

 

❖ 샘터 1개가 존재하며 위치기 -100,000,000이고, 설치해야하는 집이 100,000일 때에 불행도의 합이 최소가 될 때 가장 왼쪽에 위치하는 집이 -100,050,000이기 때문입니다.

 

즉, 집을 설치할 수 있는 공간은 -100,050,000 ~ 100,050,000입니다.

 

boolean[]으로 살펴보면 -100,050,000의 위치가 0번째 위치이기 때문에 100,050,000을 더해주면 0이 됩니다.

 

정리

 

방문 확인을 위해 필요한 인덱스 : 현재 위치 + 100,050,000

 

→ 전체 배열은 boolean[200,100,001]의 크기로 설정을 해주시면 됩니다.

 

최소 불행도 합 구하기(그래프 탐색)

 

각 샘터 위치를 기준으로 집을 설치하는 방향은 {-1, +1} 방향입니다.

 

하지만, 각 그래프 탐색을 하면서 {-1, +1}을 할 필요는 없습니다.

→ +1 ▶︎ -1  원래 위치를 탐색하는 것이지만 이동한 거리만 증가한 것이기 때문에 처음에 정해진 방향으로만 이동하는 것이 중복 탐색을 방지할 수 있습니다.

 

즉, 각 샘터 위치를 기준으로 +1, -1 방향으로 이동하는 그래프 탐색을 진행하면 됩니다.

 

❖ 샘터 위치를 기준으로 하는 것은 샘터 위치가 가까워야 불행도의 합이 낮아지기 때문입니다.

 

정리하면,

 

샘터 기준으로 그래프 탐색시, 초기 방향으로만 이동하며, K개의 집을 설치하였을 때 불행도의 합이 최소값이 된다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

N	K
2	5

 

샘터의 위치

 

 

 

 

 

 

2. 샘터를 기준으로 그래프 탐색을 진행하여 최소가 되는 불행도의 합을 탐색합니다.

 

 

초기 샘터의 위치는 집으로 설정할 수 없기 때문에 방문 처리를 진행합니다.

 

boolean[0 + 100,050,000] = true

 

booelan[3 + 100,050,003] = true

 

샘터를 기준으로 {-1, +1} 방향으로 가는 집을 추가합니다.

 

샘터에서 불행도 1인 위치로 이동

해당 위치 {-1, 1, 2, 4} 의 집이 위치하게 됩니다.

 

현재 설치한 집의 개수 : 4개

 

샘터에서 불행도 2인 위치로 이동

 

집이 위치할 수 있는 공간 {-2, 5}가 존재하지만 1개의 집만 더 위치시키면 되기 때문에 1개의 위치에만 집이 설치됩니다.

 

거리가 1인 집 : 4개(불행도 합 : 4)

 

거리가 2인 집 : 1개(불행도 합 : 2)

 

 

3. 탐색을 통해 얻은 불행도의 최소합을 결과로 출력합니다.

 

불행도 낮은 위치부터 집을 배치시켰을 경우, 얻을 수 있는 불행도의 최소합

 

4(거리가 1인 집) + 2(거리가 2인 집) = 6

 

6 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer을 이용해서 샘터 정보를 띄어쓰기 기준 나누었습니다.
• search를 통해서 샘터를 기준으로 K개 집에 대한 불행도 최소 합을 탐색합니다.
• 탐색을 통해 얻은 불행도 최소합을 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• search 함수는 그래프 탐색을 통해서 샘터 기준 불행도가 낮은 집의 위치를 먼저 탐색합니다.
• search 함수는 불행도 낮은 K개의 집에 대한 불행도 합을 결과로 반환합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    //그래프 탐색에 필요한 정보 가진 내부 클래스
    static class Info{
        //site : 위치, distance : 이동한 거리,  dir : 방향
        int site, distance, dir;

        public Info(int site, int distance, int dir) {
            this.site = site;
            this.distance = distance;
            this.dir = dir;
        }
    }
    //집 위치 가능 여부 확인 배열
    static boolean[] visited = new boolean[200100001];
    //방문 확인 인덱스 추가되는 값
    static final int PLUS_INDEX = 100050000;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine()," ");
        int[] sites = new int[N];
        //샘터 정보 저장 및 집 위치 불가능하도록 설정
        for (int i = 0; i < N; i++) {
            sites[i] = Integer.parseInt(st.nextToken());
            visited[sites[i]+PLUS_INDEX] = true;
        }
        //그래프 탐색으로 최소 불행도의 합 구하기
        long answer = search(sites, K);
        //최소 불행도의 합 BufferedWriter 저장
        bw.write(String.valueOf(answer));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //그래프 탐색으로 샘터 기준 탐색하여 불행도 최소 합 구하는 함수
    static long search(int[] sites, int K){
        long result = 0;
        int count = 0;
        Queue<Info> q = new ArrayDeque<>();
        //각 샘터 기준 {+1, -1} 방향 집 위치 초기 설정
        for(int site : sites){
            q.add(new Info(site, 1, 1));
            q.add(new Info(site, 1, -1));
        }
        //BFS 탐색 진행
        while(!q.isEmpty()){
            //K개의 집 위치 설정 완료
            if(count == K){
                break;
            }
            Info info = q.poll();
            //현재 다음 이동할 공간
            int nxtSite = info.site + info.dir;
            //집을 설치할 수 있는 공간일 때
            if(!visited[nxtSite+PLUS_INDEX]){
                visited[nxtSite+PLUS_INDEX] = true;
                q.add(new Info(nxtSite, info.distance+1, info.dir));
                //불행도 더하기
                result += info.distance;
                //집 설정 개수 더하기
                count++;
            }
        }
        //불행도 최소 합 반환
        return result;
    }
}