백준

15686번 치킨배달 / Python

문제

풀이과정

입력 데이터의 최대 개수와 최대 연산량을 생각해본다.
입력 데이터의 크기가 크지 않기 때문에 시간 복잡도를 크게 고려하지 않는다.

치킨 가게와 집의 거리를 구하는 연산 과정이 필요
전체 치킨 가게 중 폐업하지 않을 치킨 가게의 개수만큼의 조합이 필요하다.

리스트의 조합

from itertools import combinations

조합을 구하고 도시의 최소 치킨 거리를 찾기 위한 기본 값을 설정
각 조합에서의 치킨 거리를 구하고 전체 조합 중 최소 치킨 거리를 구한다.

소스코드

#백준 15686번 치킨배달
n, m = map(int, input().split()) #도시크기 n, 남길 치킨 집 m

city = []

for i in range(n):
  line = list(map(int, input().split()))
  city.append(line)

home = [] #집 좌표
chicken = [] #치킨 가게 좌표

#좌표 구하기
for i in range(n):
  for j in range(n):
    if city[i][j] == 1:
      home.append((i+1, j+1))
    if city[i][j] == 2:
      chicken.append((i+1, j+1))


#하나의 치킨 집에서 각 집 까지의 거리
chicken_dsit=[[0] * len(home) for _ in range(len(chicken))]

for i in range(len(chicken)):
  for j in range(len(home)):
    dist = abs(chicken[i][0] - home[j][0]) + abs(chicken[i][1] - home[j][1])
    chicken_dsit[i][j] = dist

    
#리스트에서 조합 구하기
from itertools import combinations

result = 999999

for combination in combinations(chicken_dsit, m):
  temp = 0
  for i in range(len(home)):
    min_dist = 999
    for j in range(m):
      min_dist = min(min_dist, combination[j][i])
    temp += min_dist
  result = min(result, temp)

print(result)