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

Problem

치킨거리의 합이 최소인 거리의 합을 찾는 문제
1이 집
2가 치킨
치킨 가게의 후보군을 최대로 정해 집<->치킨과의 거리의 합의 최소값을 찾는 문제

Solution

사실 그냥 구현 문제임. 그런데 for문의 순서를 잘못 설정하면 시간이 꽤나 걸림.

또한, 치킨가게의 후보지가 M만큼 주어지면 M을 최대로 다쓰면된다.

나는 이 M도 1부터 돌려서 판별하느라 시간이 초과됨. 치킨가게는 최대한 많이 두면 가까워질테니까...

코드설명

1)1이 집 2가 치킨가게이므로 이를 배열에 담음

2)치킨가게중 M개의 치킨가게의 조합을 생성해야하므로 combination을 이용(단 최소거리라 하더라도 M을 최대로 다쓰면 그게 최소거리..)

3)

for 치킨의 후보집중 in 치킨의 모든집:
	for 집 하나하나 in 모든집:
    	for 치킨 후보 좌표들 in 치킨 후보집:
        	minValue=min(하나하나들<->후보들간의 거리의 최소값)
        minValue는 후보하나당 각 집에 가는 최소값
        res+=minValue(집<->가게 거리)
    result.append(res)후보군들 모아서 min값구하려고 append

Python Code

import sys
from itertools import combinations
N,M=map(int,sys.stdin.readline().split())

graph=[]
chikenList=[]
houseList=[]
for _ in range(N):
    tmp=list(map(int,sys.stdin.readline().split()))
    graph.append(tmp)
for i in range(0,len(graph)):
    for j in range(0,len(graph[i])):
        if graph[i][j]==2:
            chikenList.append((i,j))
        if graph[i][j]==1:
            houseList.append((i,j))

chikenList=list(combinations(chikenList,M))


result=[]



for chiken in chikenList:
    res=0
    for house in houseList:
        tmp=1e9
        for a,b in chiken:
            tmp=min(tmp,abs(a-house[0])+abs(b-house[1]))
        res+=tmp
    result.append(res)
print(min(result))