[Python] 18513 샘터

[Gold IV] 샘터 - 18513 

[문제 링크](https://www.acmicpc.net/problem/18513)

---

💻 문제 정의

일직선 상의 공간에 N개의 샘터가 존재하고, K채의 집을 지으려고 한다. 하나의 집과 가장 가까운 샘터까지의 거리를 특정 집의 불행도라고 하는데, 모든 집에 대해서 불행도의 합이 최소가 되도록 하는 값을 구하는 문제이다.

💡 접근 및 설계

샘터를 기준으로 양 옆으로 집을 배치하는 것이 불행도가 최소가 되는 방법이다. 최대한 샘터에 가깝게 집을 배치할 수 있도록, 집을 배치할 수 있는 점을 너비우선탐색으로 찾는다.

✏️ 알고리즘 풀이

Q = deque()
visited = dict()

for p in pool:
    Q.append(p)
    visited[p] = 0

탐색을 위한 deque()와 샘터의 거리를 먼저 저장한다.

cnt = 0
ans = 0

while Q:
    curr = Q.popleft()

    for next_point in [curr-1, curr+1]:

        if next_point not in visited.keys():
            visited[next_point] = visited[curr] + 1
            ans += visited[next_point]
            cnt += 1

            if cnt == K:
                print(ans)
                exit()
        
            Q.append(next_point)

샘터를 기준으로 탐색을 이어나가며 집을 배치한다. 모든 집을 배치하고 나면 코드를 멈춘다.

🗒️ 최종 제출 코드

# 18513 샘터

from collections import deque

N, K = map(int, input().split())
pool = list(map(int, input().split()))

Q = deque()
visited = dict()

for p in pool:
    Q.append(p)
    visited[p] = 0

cnt = 0
ans = 0

while Q:
    curr = Q.popleft()

    for next_point in [curr-1, curr+1]:

        if next_point not in visited.keys():
            visited[next_point] = visited[curr] + 1
            ans += visited[next_point]
            cnt += 1

            if cnt == K:
                print(ans)
                exit()
        
            Q.append(next_point)

 

---

💭 오늘의 회고

-