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

문제 링크:

 

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

15686번: 치킨 배달

 

 

치킨 배달

 

 

---

풀이 과정:

 

이 문제는 기존에 존재하는 치킨집을 줄여서 최대 M개로 유지하면서, 일반 집들로부터 M개의 치킨집까지의 거리를 줄이는 것이 목표이다. 이후 도시의 치킨 거리의 최솟값을 계산하면 된다. 

 

<문제 풀이를 위한 테크닉>

1. N개의 치킨집 중 M개를 골라야 한다면 조합을 이용한다. 파이썬에서 조합(combinations) 라이브러리를 제공하므로, 이를 이용하면 모든 경우를 간단히 계산할 수 있다.

2. 치킨 집 중 M개를 고르는 모든 경우에 대해서 치킨 거리의 합을 계산하고(완전 탐색), 치킨 거리의 최솟값을 구해 출력하면 된다.

 

풀이 코드:

 

# 15686번 치킨 배달

# 1. 집, 치킨집 좌표 구하기
# 2. 조합을 이용하여 특정 치킨집 생성
# 3. 집과 치킨집 사이의 최소 거리 합을 구하는 함수 생성
# 4. 도시의 치킨 거리가 최솟값 출력

from itertools import combinations

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

house, chicken = [], []

# 집, 치킨집 좌표 구하기
for i in range(n):
  data = list(map(int, input().split()))
  for j in range(n):
    # 입력받은 데이터가 집이라면 현재 좌표를 집 리스트에 추가
    if data[j] == 1:
      house.append((i, j))
    # 입력받은 데이터가 치킨집이라면 현재 좌표를 치킨집 리스트에 추가
    elif data[j] == 2:
      chicken.append((i, j))

# 도시에 있는 치킨집 중 m개를 골라 영업 후보지로 선정 
candidates = list(combinations(chicken, m))

# 집과 치킨집 사이의 최소 거리 합을 구하는 함수
def get_sum(candidate):
  result = 0
  # 모든 집에 대하여
  for hx, hy in house:
    # 가장 가까운 치킨집 찾기
    temp = 1e9
    for cx, cy in candidate:  
      temp = min(temp, abs(hx-cx) + abs(hy-cy))
    # 가장 가까운 치킨집까지의 거리 더하기
    result += temp
  return result

# 도시의 치킨 거리 최솟값 출력
result = 1e9
for candidate in candidates:
  result = min(result, get_sum(candidate))

print(result)

 

 

 

15686번 치킨 배달