[코테 스터디] 구현, 치킨 배달

Q13. 치킨 배달

🐣문제

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.


치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.


도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.


백준 링크 | https://www.acmicpc.net/problem/15686

🐥풀이

1. 집 좌표를 저장하는 배열과 치킨집 좌표를 가지는 배열 2개를 정의하고 각 좌표를 저장한다.
2. itertools의 combinations를 사용하여 치킨집 좌표 배열에서 치킨집 m개를 뽑는 모든 경우를 리스트로 저장한다.
3. 모든 집과 m개의 치킨집의 "치킨 거리"를 구하여 거리 테이블(리스트)에 저장한다.
4. 모든 경우의 치킨 거리를 구한 후, 그 중 최소 거리를 출력한다.

🐓코드

from itertools import combinations

n, m = map(int, input().split())
house = [] # 집 좌표
chicken = [] # 치킨집 좌표

for i in range(n):
  street = list(map(int, input().split()))
  for j in range(len(street)):
    if street[j]==1: # 집
      house.append([i,j])
    elif street[j]==2: # 치킨집
      chicken.append([i,j])


# 치킨거리 계산
def calculate(hx, hy, cx, cy):
  # (hx, hy) : 집 좌표, (cx, cy) : 치킨집 좌표
  result = 0
  if hx>cx:
    result += (hx-cx)
  else:
    result += (cx-hx)
  if hy>cy:
    result += (hy-cy)
  else:
    result += (cy-hy)
  return result


distance = [] # 각 케이스 거리합 (거리 테이블)

# 치킨집 m개 뽑는 케이스
for case in list(map(list, combinations(chicken,m))): 
  result = 0
  
  # 모든 집
  for hxy in house:
    hx, hy = hxy
    temp = int(1e9)
    
    # m개의 치킨집
    for cxy in case:
      cx, cy = cxy
      
      # 가까운 치킨집 거리
      temp = min(temp, calculate(hx,hy,cx,cy)) 
    
    result += temp

  # 치킨거리 추가
  distance.append(result)

# 최솟값 출력
print(min(distance))

⭐ 2022.04.07

combinations 덕에 쉽게 풀어낸 문제 :)