샘터
-
[Python] 백준 18513 샘터알고리즘/문제풀이 2021. 7. 31. 18:35
1. 문제 링크 https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 2. 문제 요약 모든 집에 대한 불행도의 합의 최솟값 구하기 3. 아이디어 정리 샘터를 기준으로 불행도를 늘려주면서 bfs를 진행한다. 샘터를 기준으로 시작하기 위해 큐에 넣어준다. -1, + 1 위치 방향으로 bfs 진행 해당 집 위치를 큐에 넣기 - (집 위치, 현재 불행도 + 1) 4. 문제 풀이 4-1. 내 풀이 import sys from c..