BOJ 백준 파이썬 18513 샘터

일단은 각 샘터의 위치를 큐에 집어 넣는다.

그리고 큐에서 꺼내서 +1,-1로 움직인다.

큐에 집어넣을때마다 갯수는 하나씩 추가하고 결과값도 누적으로 더해간다.

bfs란 말에 맞게 너비우선탐색, 거리가 1,2,3,4 순차적으로 계산해간다.

bfs의 정석 같은 문제라 생각

하지만, 이 문제에서 어려운 점은 메모리 초과

이것은 dict형으로 해결해주면 된다.

dist 배열(내 코드에서는 vist)을 dict로 선언해주고

dist[nx]=dist[x]+1식으로 문제를 해결해가면 된다.

 

 

import sys
from collections import deque
from itertools import combinations
 
if __name__=='__main__':
   # sys.stdin=open("input.txt", "rt")
 
    n,home=map(int,input().split()) ##n=샘터의 개수, k=집의 개수
 
    start=list(map(int,input().split())) ##샘터 입력 받기
 
  
    max_x=100000000 
   
    ##출발점 큐에 집어넣기
    res=0
    cnt=0
    visit=dict()
    q=deque()
    ##샘터 배치
    for x in start:
        if -max_x<=x<=max_x:
            visit[x]=0
            q.append(x)
 
    dx=[-1,1]
    ##집 배치
    cnt=0
    while q:
       x=q.popleft()
       #print(x)
       for k in range(2):
           nx=x+dx[k]
 
           if nx not in visit:
                  #print(visit)
                  visit[nx]=visit[x]+1
                  q.append((nx))
                  res+=visit[nx]
                  cnt+=1
          
           ##집을 다 채웠으면 출력
           if cnt==home:
               print(res)
               exit()