[백준/python] 치킨 배달

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

15686번: 치킨 배달

---

[알고리즘]

일단 치킨집이랑 가정집이 어디에있는지 좌표를 저장해준다.

c, h = [], []
for i in range(n) : 
    for j in range(n) : 
        if city[i][j] == 1 : h.append((i,j))
        elif city[i][j] == 2 : c.append((i,j))

 

치킨집 M개를 골라서 해당 치킨집이 위치한 좌표들과 가정집의 좌표들을 비교하여 거리를 측정해준다. 이때 가정집 좌표 한 점에서 m개의 치킨집과의 거리를 둘러봐야 하기 때문에 가정집이 바깥 for문, 치킨집이 내부 for문이다. 안쪽 for문을 돌면 가정집 1에서부터 m개의 치킨집까지 거리를 비교하여 최소거리만 남게 된다. 이를 res에 누적하여 도시의 치킨 거리를 구한다.

chicken_m = cb(c, m)

for m in chicken_m : 
    # 고른 M개의 좌표와 home을 비교하면서 가장 가까운 c 찾기
    res = 0
    for hx, hy in h : 
        dist = float('inf')
        for cx, cy in m :
            dist = min(dist, abs(hx-cx)+abs(hy-cy))
        res += dist
    ans = min(ans,res)

---

[전체 코드]

from itertools import combinations as cb

n,m = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(n)]
ans = float('inf')

# 치킨집, 가정집 좌표 저장
c, h = [], []
for i in range(n) : 
    for j in range(n) : 
        if city[i][j] == 1 : h.append((i,j))
        elif city[i][j] == 2 : c.append((i,j))

# 전체 c 중에 M개만 선택해야 함
chicken_m = cb(c, m)
print(list(chicken_m))
for m in chicken_m : 
    # 고른 M개의 좌표와 home을 비교하면서 가장 가까운 c 찾기
    res = 0
    for hx, hy in h : 
        dist = float('inf')
        for cx, cy in m :
            dist = min(dist, abs(hx-cx)+abs(hy-cy))
        res += dist
    ans = min(ans,res)
print(ans)