[BOJ/백준] 18513 쉼터

import sys
from collections import deque
def input():
    return sys.stdin.readline()
N,M = map(int,input().split())

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

visited_set = set(sams)

queue = deque()
for sam in sams:
    queue.append((sam,0))

cnt = 0
result = 0
while queue:
    cur_node,dis = queue.popleft()
    result += dis
    cnt += 1
    if cnt == N+M:
        break
    for next_node in [cur_node+1,cur_node-1]:
        if next_node not in visited_set:
            visited_set.add(next_node)
            queue.append((next_node,dis+1))
print(result)

이 문제는 샘터를 기준으로 bfs를 하면서, 방문 표시를 해주면 되는 문제였다.

 

종료조건은 샘터의 개수와 집의 개수를 합친 개수가 되면 종료가 되게 하면 된다.