백준 18513번: 샘터 (Python/Java)

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

18513번: 샘터

 

 

 

접근

---

이 문제에서 물어보는 것은 불행도의 합이 가장 적은 방법으로 집을 위치시키고, 불행도를 구하라는 것이다. 문제만 읽어봐도 알 수 있듯이 말만 불행도라고 했지, 결국 샘터와 가장 가까운 집들의 거리합을 구하는 문제다.(애초에 문제에서 집의 불행도는 샘터와의 거리로 정의된다고 적어놨다) 가장 가까운 거리의 합을 구하는 전형적인 너비우선탐색 문제라고 볼 수 있다.

 

그렇다면 가장 가까운 거리의 합은 어떻게 구할까? 탐색에 사용할 큐에 모든 샘터들의 위치를 넣는다. 그리고 하나씩 꺼내 양 옆에 샘터, 혹은 집이 있는지 살펴보고 있다면 넘어가고 없다면 위치를 체크한 뒤 해당 위치를 큐에 넣어준다. 이를 반복하다 보면 구해야 하는 집의 수만큼 체크할 수 있을 것이고 그때 탐색을 끝낸 뒤, 거리 합을 출력하면 된다.

 

여기서 주의할 것이 샘터의 범위 조건이다. 샘터의 범위는 -100,000,000과 100,000,000 사이라고 나와있다. 다시 한번 말하지만 이는 샘터의 범위 조건이다. 집은 이 범위 밖을 벗어나도 상관없다. 이 문제는 집 위치 범위가 따로 없기 때문에 범위는 신경 쓰지 않아도 된다. 이 부분만 짚고 넘어가면 어렵지 않게 답을 맞힐 수 있다.

 

 

 

풀이

---

Python

from collections import deque

waterNum, houseNum = map(int, (input()).split())
waterList = list(map(int, (input()).split()))

visitList = {}
bfsDeque = deque()
for i in range(waterNum):
    visitList[waterList[i]] = True
    bfsDeque.append([waterList[i], 0])

leftRight = [-1, 1]

result = 0
thisHouse = 0
while True:
    thisDeque = bfsDeque.popleft()

    for i in range(2):
        subIdx = (thisDeque[0] + leftRight[i])

        if not subIdx in visitList:
            visitList[subIdx] = True
            bfsDeque.append([subIdx, (thisDeque[1]+1)])
            thisHouse += 1

            if thisHouse <= houseNum:
                result += (thisDeque[1] + 1)
            else:
                break
    
    if thisHouse >= houseNum:
        break

print(result)

 

Java

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException{

        String[] firstLine = (br.readLine()).split(" ");
        int waterNum = Integer.parseInt(firstLine[0]);
        int houseNum = Integer.parseInt(firstLine[1]);
        
        String[] secondLine = (br.readLine()).split(" ");
        HashMap<Integer, Boolean> visitList = new HashMap<Integer, Boolean>();
        Queue<int[]> bfsQueue = new LinkedList<>();
        for(int i = 0 ; i < waterNum ; i++){
            visitList.put(Integer.parseInt(secondLine[i]), true);
            bfsQueue.add(new int[] {Integer.parseInt(secondLine[i]), 0});
        }

        int[] leftRight = {-1, 1};

        long result = 0;
        int thisHouse = 0;
        loop:
        while(true){
            int[] thisQueue = bfsQueue.poll();

            for(int i = 0 ; i < 2 ; i++){
                int subIdx = (thisQueue[0] + leftRight[i]);

                if(!visitList.containsKey(subIdx)){
                    visitList.put(subIdx, true);
                    bfsQueue.add(new int[] {subIdx, (thisQueue[1]+1)});
                    thisHouse++;

                    if(thisHouse <= houseNum){
                        result += (thisQueue[1] + 1);
                    }else{
                        break loop;
                    }
                }
            }
        }

        System.out.println(result);

    }

}

 

 

 

후기

---

요 근래 일주일 하고도 며칠 그리디 문제만 풀었더니 너비우선탐색이 땡겨 풀어봤다. 구현이 조금 복잡할 수는 있어도 역시 그래프 문제가 재밌긴 한 것 같다.

 

한 가지 찜찜한 부분이 있는데, 탐색 영역 체크 구현이다. 범위 조건이 따로 없는 문제다 보니 따로 배열을 만드는 방법 같은 것들은 사용할 수 없었다. 그렇다고 체크를 안 할 수는 없어 생각해낸 부분이 파이썬의 경우엔 dict를, 자바의 경우엔 hashmap을 사용한 것이었다. 탐색한 위치의 인덱스를 키 값으로 설정해 추가해주고 해당 키 값이 dict 혹은 hashmap에 있는지 없는지를 확인해 탐색 여부를 체크했다. 어쨌든 정답 처리가 되긴 했지만 이렇게 풀어도 되는지, 조금 더 좋은 방법이 있는지 생각해봐야겠다.