악곱 == 악성곱슬

BFS, 해시(집합)

---

이 문제는 샘터의 위치에서 가까운 곳에 집을 지어야 한다. 따라서 가까운??? 그러면 BFS로 탐색을 하면 되겠네~~ 라고 생각하면 된다.

그런데 BFS라고 하면 우리가 방문한 노드를 주로 visited 배열을 통해 구현하는데, 여기서 범위가 무려 2억이다. 이를 모두 선언하고 풀기에는 벅차다. 따라서 집합 자료구조를 사용해서 해당 좌표를 넣어놓고 방문 여부를 체크하면 된다.

그리고 해당 문제에서 샘터의 범위만 2억이고 집은 그 밖으로 이동하며 지을 수 있다. 이 것 때문에 헷갈렸다.

구현

---

import sys
from collections import deque

def bfs(home_cnt):
    visited = set()
    que = deque()
    for f in fountain:
        que.append([f, 0])
        visited.add(f)

    answer = 0
    while True:
        cur, dist = que.popleft()
        for i in range(2):
            nxt = cur + dx[i]
            cost = dist + 1
            if nxt in visited:
                continue
            answer += cost
            home_cnt -= 1
            if home_cnt == 0:
                return answer
            que.append([nxt, cost])
            visited.add(nxt)

if __name__ == "__main__":
    MIN, MAX = -int(1e8), int(1e8)
    N, K = map(int, sys.stdin.readline().rstrip().split())
    fountain = list(map(int, sys.stdin.readline().rstrip().split()))
    dx = [-1, 1]
    print(bfs(K))