백준 15686번 치킨 배달 C++

 

1. 문제 설명

크기가 N x N인 도시가 있다.

도시의 각 칸은 빈칸과 치킨집, 집 중 하나로 되어있다.

0 = 빈칸 , 1 = 집, 2 = 치킨집으로 되어있다.

도시의 각 칸은 (r,c)와 같은 형태로 r행 c열로 나타낸다.

각각의 집에서 가장 가까운 치킨 거리가 존재하는데

집에서 치킨집의 거리는 (r1 - r1) + (c1 - c2)를 절대값으로 표현한다. 

 

가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 m개 이다.

도시에 있는 치킨집 중에서 m개를 선택해 나머지를 전부 폐업한다고 하였을 때,

도시의 치킨 거리가 가장 작게 되는지를 구한다.

도시의 치킨 거리는 , 도시에 있는 집에서의 치킨집과의 거리를 구한 값을 모두 더한값이다.

 

dfs 백트래킹을 통해 치킨집을 골라 조합 선택을 하며 반복해 가장 작읍 값을 구한다.