[백준/파이썬] 15686 치킨 배달

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

---

알고리즘 분류

• 브루트포스

문제풀이

M개 치킨집으로 모든 집의 치킨거리를 최소로 하는 값을 구해야 한다.

먼저 집과 치킨집의 위치를 각각 리스트에 저장하고 치킨집중에서 m개만 골라 조합을 통해 리스트를 만들어준다.
그리고 result리스트는 각 조합에 따른 거리의 최소값을 저장한다.

ex)
pick_chicken=[((0, 1), (3, 0)), ((0, 1), (4, 0)), ((0, 1), (4, 1)), ((0, 1), (4, 4)), ((3, 0), (4, 0)), ((3, 0), (4, 1)), ((3, 0), (4, 4)), ((4, 0), (4, 1)), ((4, 0), (4, 4)), ((4, 1), (4, 4))]
i=(0,3) ...
pick_chicken[j]=((0,1),(3,0)) ...
k=(0,1), (3,0) ...

소스코드

from itertools import combinations

n,m=map(int, input().split())
maps=[]
for i in range(n):
  maps.append(list(map(int, input().split())))

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

pick_chicken=list(combinations(chicken,m))
result=[0]*len(pick_chicken)

for i in home:
  for j in range(len(pick_chicken)):
    a=100
    for k in pick_chicken[j]:
      temp=abs(i[0]-k[0])+abs(i[1]-k[1])
      a=min(a,temp)
    result[j]+=a

print(min(result))