백준 15686 치킨 배달

https://www.acmicpc.net/problem/15686

 

치킨집 좌표와 집 좌표를 리스트에 저장했다.

그 후에 치킨집 좌표 m개를 고르고 , 치킨 거리를 계산하도록 했다. 도시의 치킨 거리는 당연히 치킨집개수Cm 만큼 나올 것이다. 그 중에서 가장 작은 값을 출력하면 된다. 

n,m = map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
chicken =list()
home = list()
ans =list()
result = list()


for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            home.append((i+1,j+1))
            
        if graph[i][j] == 2:
            chicken.append((i+1,j+1))



def cal(m_chicken,home):   # 치킨집개수Cm개 도시의 치킨거리 계산  (집과 가장 가까운 치킨집 사이의 거리)
    ans =0
    for a,b in home:
        degree = 1e9
        for c,d in m_chicken:
            degree= min(degree,abs(a-c)+abs(b-d))
        ans +=degree
    return ans


def choose(num,start): # 치킨집 좌표 중 m개 뽑기
    if num == m :
        result.append(cal(ans,home)) # 거리계산 배열
        return
    for i in range(start,len(chicken)):
        ans.append(chicken[i])
        choose(num+1,i+1)
        ans.pop()

choose(0,0)    

print(min(result)) # 배열 중 최소값