골드 V

💡문제 분석 요약

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

Brute Force로 풀었고

Back Tracking도 가능하다.

💡알고리즘 설계

최대 M개가 이미 정해져 있으니, M개의 치킨집을 고르는 전체 경우의 수를 전부 구하고, 각 경우마다의 치킨거리를 구해서 가장 작은 값을 출력한다.

M의 최댓값이 13이므로 나올 수 있는 경우의 수가 엄청나게 크지는 않다고 판단하여 itertools 의 combinations를 활용하여 풀었다.

각 집을 하나 씩 돌면서 각 치킨집까지의 치킨거리를 구해 가장 작은 값을 구하여 dist에 넣고 최솟값을 구하는 식으로 풀었다.

💡코드

import sys 
from itertools import combinations
import math
input = sys.stdin.readline

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

street = []
chicken = []
home =[]

for _ in range(n):
    street.append(list(map(int,input().strip().split())))
    
for i in range(n):
    for j in range(n):
        if street[i][j]==2:
            chicken.append((i,j))
        elif street[i][j]==1:
            home.append((i,j))
test = []

if m != len(chicken):
    select = combinations(chicken,m)
else:
    select = [chicken]

MINS = math.inf
for chi_store in select:
    dist = 0
    for h in home:  #각 집을 돌면서 치킨 거리 구하기
        min_d=math.inf
        for c in chi_store:
            min_d=min(min_d,abs(c[0]-h[0])+abs(c[1]-h[1]))
        dist +=min_d
    MINS = min(dist,MINS)

print(MINS)

💡 기억할 것

  • back tracking으로도 풀어보자!
  • 각 코들 작성할 때 어떤 데이터를 다루고 있는지 주석으로 달아서 명확히 하자.