[Baekjoon] 15686번 치킨배달 / Python

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

15686번: 치킨 배달

 

내가 생각한 풀이 과정

1. 치킨집(chicken)과 집(home)의 좌표를 따로 계산한다
2. combinations 라이브러리를 활용해서 치킨집의 좌표를 m개를 가져온다.
3. m개의 치킨집과 집과의 거리를 비교해서 더해준다
4. 그중 가장 짧은 거리를 치킨거리로 설정한다

from itertools import combinations

def distance(a, b) :
    x1, y1 = a
    x2, y2 = b
    return abs(x1-x2) + abs(y1-y2)

n, m = map(int, input().split())

chicken = []
home = []
for i in range(n) :
    for ind, j in enumerate(input().split()) :
        if j == '1' :
            home.append((i, ind))
        elif j == '2' :
            chicken.append((i, ind))

dis = int(1e9)
for lists in combinations(chicken, m) :
    tmp = 0
    for i in home :
        dist = [distance(i, j) for j in lists]
        tmp += min(dist)
    dis = min(tmp, dis)

print(dis)