[백준 18513번] 파이썬 - 샘터

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

 

접근 방법

1. 문제에서 샘터의 범위가 -1억 ~ 1억까지이다. 큰 범위이므로, 위치의 크기만큼 리스트를 생성하면 메모리 또는 시간 초과가 날 것이다.

2. 따라서, visited 배열이 아닌 set을 활용하여 방문한 곳을 기록해준다.

3. 각 쉼터에서 1칸씩, 2칸씩 갈 수 있는 곳을 점차 넓혀 나가는 것이 최소의 값을 구하는 방법이므로 bfs를 이용하여 풀어준다.

4. q에는 (시작위치, 현재 위치)를 담아주고, 각 쉼터에서 -1, +1을 한 곳을 방문하지 않았다면 q에 담아준 후 result에 거리 차이만큼 +, 남은 집의 갯수를 -1 해주면 된다.

 

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from queue import deque

def main():
    global N, K, rests
    q = deque()
    visited = set()
    for i in rests:
        q.append((i, i))
        visited.add(i)

    result = 0

    while q:
        st, now = q.popleft()
        for d in [-1, 1]:
            next = now + d
            if not next in visited:
                result += abs(st - next)
                visited.add(next)
                q.append((st, next))
                K-=1
            
            if (K <= 0):
                print(result)
                return

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