백준 15686번 치킨 배달

< 백준 15686번 치킨 배달 - 마포 코딩박>

사용한 알고리즘: DFS + 완전탐색


 치킨집을 (최대) M개만 남겼을때 도시의 치킨거리의 최솟값을 구하는 문제입니다.
저는 치킨집을 없애는 모든 경우를 DFS 를 돌려 답을 구했습니다.

문제풀이는 다음과 같습니다.
(1) (코드: 38~49)
 입력받을 때, 집의 위치, 치킨집 위치를 각각 pair 로 저장했습니다.
 없애야 되는 치킨집 수를 CNT 로 놓고 DFS를 돌립니다.

(2) (코드: 11~12)
 위치 A 와 B 사이의 거리를 문제에서 주어진 공식으로 구하는 함수를 만들었습니다.

(3) (코드: 14~34)
 과정 (1)에서 따로 모아둔 치킨집을 차례로 보면서,
 1. x번째 치킨집을 없애지 않고 x+1번째로 재귀
 2. x번째 치킨집을 없애고 (set에 저장) x+1번째로 재귀
 과정을 통해 DFS 를 돌렸습니다.
 없앤 치킨집이 CNT 인 경우 도시의 치킨거리를 계산해주었습니다.