일직선 상에서 특정 위치에서 거리 합이 최소가 되도록 집을 짓는 문제

18513번: 샘터

 

N개의 샘터가 주어질때 K채의 집을 지을려고 한다

 

각 집에서 가장 가까운 샘터까지의 거리를 불행도라고 정의할때 K채의 집의 모든 불행도의 합이 최소가 되도록 집을 짓는다

 

그 불행도의 합의 최소를 구하는 문제

 

-------------------------------------------------------------------------------------------------------------------

 

BFS로 풀 수 있다는데 생각해봐도 감이 잘 안오더라고... 평소 BFS문제랑 조금 달라서 그런지

 

샘터 위치 x에서 왼쪽 오른쪽으로 -1,1만큼 봐서 비어있으면 x-1, x+1에 집을 짓고

 

다시 x-1에서 왼쪽 오른쪽으로 -1,1만큼 x-1,x에서 비어있으면 집을 짓고

 

x+1에서 왼쪽 오른쪽으로 -1,1만큼 x,x+1에서 비어있으면 집을 짓고

 

....

 

이를 반복하면 될것 같다

 

처음에 샘터 위치 x를 모두 큐에 넣은 다음 큐에서 위치 하나씩을 빼서 왼쪽 오른쪽 -1,1만큼만 봐서

 

비어있으면 집을 지은 다음 그 위치를 큐에 다시 넣어준다

 

집을 짓는데 성공했다면 카운팅을 해주고 샘터에서까지 거리를 누적해준다

 

총 K채를 짓는데 성공했다면 반복을 멈추면 끝

 

집을 짓는데 성공했다면 그 집은 확실히 가장 가까운 집중 하나이기 때문에 카운팅을 해주면 됨

 

그리고 샘터에서까지 거리는 처음에 샘터 위치를 큐에 넣을 때 (x,0)으로 넣어주고

 

매 행위마다 1씩 증가시켜서 (x,c+1)을 넣어주면 현재 샘터에서까지 거리를 알 수 있을 것

 

-------------------------------------------------------------------------

 

근데 그 집을 짓는 위치가 더 가까운 샘터가 있을 수도 있는거 아님?

 

그랬으면 이미 그 위치는 다른 샘터에 의해 집이 지어져있는 곳일거라 그런 경우는 불가능하다

 

그리고 visited 체크할 때는 어떻게 해야하지

 

샘터 위치 범위가 -10^8에서 10^8이다보니 단순히 배열로 만들면 메모리 초과날것

 

좌표 압축을 시도해볼 수도 있긴한데 어차피 n이 10만이라 굳이 그래야하나 

 

hash나 set으로 저장을 하면 된다 그러면 O(1)에 확인 가능

 

from collections import deque

n,k = map(int,input().split())

A = list(map(int,input().split()))

visited = {}
queue = deque([])

#(샘터 위치, 샘터까지 거리)를 모두 큐에 넣고
for i in range(n):
    
    visited[A[i]] = 0
    queue.append((A[i],0))

count = 0
v = 0

while queue:
    
    x,c = queue.popleft()
    
    #현재 위치에서 왼쪽 -1, 오른쪽 +1 부분을 확인
    #비어있으면 집을 짓고 샘터까지 거리 c+1를 누적해줌
    #집을 짓는데 성공하면 1씩 counting해서 총 k개 지으면 끝
    if visited.get(x-1,-1) == -1:
        
        visited[x-1] = 1
        v += c+1
        queue.append((x-1,c+1))
        count += 1
    
    if count == k:
        
        break

    if visited.get(x+1,-1) == -1:
        
        visited[x+1] = 1
        v += c+1
        queue.append((x+1,c+1))
        count += 1
    
    if count == k:
        
        break

print(v)