백준 알고리즘 15686: 치킨 배달 (Python)

 

15686번: 치킨 배달

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

문제

---

문제 해결을 위한 과정

이 문제의 경우 가장 중요했던 것은 조합 즉 combination을 이용하는 것이었습니다. 만일 a, b, c, d, e라는 5개의 치킨집이 있을 때 3개를 뽑는 경우라면 a, b, c와 a,c,b와 b,a,c와 b,c,a 등등 이렇게 뽑은 것이라면 같은 경우입니다. 즉 순서가 중요하지 않은 조합을 이용하여 해결하는 것입니다. 파이썬에서 조합을 사용하기 위해서는 다음의 코드를 추가합니다.

from itertools import combinations

이 방법을 통해 치킨집들중 입력받은 M개를 고른 후 각각의 집마다 치킨 거리를 구한 후 도시의 최소 치킨 거리를 구하면 됩니다.

---

문제 해결을 위한 팁

None

소스코드

town.append(list(map(<span

from itertools import combinations
 
def compute(data):
  answer = 0
  for i in range(len(house)):
    a, b = house[i]
    temp = int(1e9)
    for x, y in data:
      temp = min(temp, abs(x - a) + abs(y - b))
    answer += temp
  return answer
 
N, M = map(int, input().split())
town = []
house = []
store = []
 
for i in range(N):
  town.append(list(map(int, input().split())))
  for j in range(N):
    if town[i][j] == 1:
      house.append((i, j))
    elif town[i][j] == 2:
      store.append((i, j))
 
ans = int(1e9)
for data in combinations(store, M):
  ans = min(ans, compute(data))
 
print(ans)