백준 15686

1. 좌표 저장

어떻게 풀까 고민하다가 우선 1 (집), 2(치킨집)으로 된 각 좌표를 저장하였다.

 

2. 각 치킨집에서 집까지의 거리 구해 배열에 저장

그 후, 각 치킨집에서 집까지의 거리를 구해 distance_per_chickenshop 배열에 저장하였다.

 

입력이 아래와 같을 때 distance_per_chickenshop의 출력 결과는 다음과 같다.

즉, 3개의 치킨집에 임의로 번호를 붙였을 때, 3개의 각 치킨집에서 4개의 집까지의 각 거리를 구한것이다. 

(원소 0번째: 1번 치킨집에서 1-4번 집까지의 거리, 원소 1번째: 2번 치킨집에서 1-4번 집까지의 거리....)

 

3. 치킨집 수 C m 으로 모든 치킨집 조합 구하기

치킨집이 최대 m개가 존재할 수 있다는 소리는, 치킨집이 1개부터 m개까지 있을 수 있단 소리다. 

만약 치킨집이 최대 3개가 존재할 수 있다면, 치킨집이 1개도 폐업을 안 해서 3개가 남을 수도, 혹은 폐업을해서 2개나 1개만 남을 수 있다.

(1번 치킨집만 남거나, 1번과 2번이 남거나, 1번과 3번이 남거나, 1번 2번 3번 모두 남거나)

 

따라서 가능한 치킨집의 조합을 itertools.combinations로 구한다. 

이후 각 조합에서 각 집에서 치킨집까지의 거리를 비교해 최솟값을 구해야 한다.

 

4. 조합으로 나온 각 결과에서, 각 집에서 치킨집까지의 최소 거리를 구한다.

예로, 1번과 2번 치킨집만 남는 조합이라면 최소 치킨 거리는 아래와 같이 구한다. 

1번 치킨집의 치킨거리: [1, 2, 2, 2]

2번 치킨집의 치킨거리: [2, 3, 1, 1]

 

=> 1번 집의 입장에서 1번 치킨집이 더 가깝고, 2번 집의 입장에서도 1번 치킨집이 더 가깝다. 

=> 각 집에서 치킨집까지 걸리는 최소 거리를 구해야 하므로 min 함수를 사용한다. 

그 결과, 선택되는 치킨 거리는 [1, 2, 1, 1]이 될 것이다.

 

5. 모든 조합에서의 최소 치킨 거리를 구한다.

위의 치킨 거리를 모두 더하면 각 조합의 최소 치킨 거리가 구해진다. (city_chicken_distance)

우리는 모든 조합에서 최소의 거리를 구해야 하므로, city_chicken_distance들이 저장된 city_chicken_distances[] 의 최소값을 구한다. 

 

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

city=[]
chickens=[]
homes=[]
distance_per_chickenshop=[]

for i in range(n):
    city.append(list(list(input().split())))
    for j in range(n):
        if city[i][j]=='2':
            chickens.append((i+1,j+1))
        elif city[i][j]=='1':
            homes.append((i+1, j+1))

distance_per_chickenshop=[[(abs(h[0]-c[0])+abs(h[1]-c[1])) for h in homes] for c in chickens]

city_chicken_distances=[]
for i in range(1, m+1):
    # 치킨집을 조합으로 나타내어, m보다 작은 치킨집 조합을 모두 구하기
    nCr_chicken = list(itertools.combinations(distance_per_chickenshop, i))
    for combi in nCr_chicken:
        city_chicken_distance=0
        for j in range(len(homes)):
            distance_per_home=[]
            for k in range(len(combi)):
                distance_per_home.append(combi[k][j])
            #1번 치킨집에서 1번집까지의 거리 vs 2번 치킨집에서 1번집까지의 거리 => 그 중 최값들끼리 더함
            #즉, 각 집에서 치킨집까지의 거리를 비교하고 그 중 최솟값을 찾는것이다.
            city_chicken_distance+=min(distance_per_home)
        city_chicken_distances.append(city_chicken_distance)
"""
근데...for문을 4번이나 중첩해 써서 효율성은 떨어지는 코드이다. 
"""
print(min(city_chicken_distances))