[구현] 치킨 배달

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 1시간 30분 + a

1. 문제 설명

- 치킨 가맹점 수를 획기적으로 줄일 수 있는 방법을 고안하던 중, 거리를 활용한 방법을 이용해 가맹점 수를 줄이고자 한다.

- 최소 가맹점 수를 남기고자 할 때, 모든 집에서 치킨집까지의 거리가 최소가 되게 하는 방법

2. 접근 방식

- 각 집에서의 치킨 거리를 구하는 게 가장 중요할 거 같다고 생각
- 수익을 많이 낼 수 있는 치킨집의 개수는 M개이고, 치킨집을 'M'개만 남긴다가 핵심이 되겠다.

1. 치킨집 리스트를 만든다.
2. 치킨집의 행, 열 정보를 담은 리스트를 만든다.
3. 각 치킨집 하나, 하나에 대한 '도시의 치킨 거리'를 구한다. 
4. 도시의 치킨거리가 가장 큰 거를 다 지우고 N개만 남긴다.
5. N개의 치킨 거리에 대한 각 집의 거리를 min()으로 구한다.
6. 다시 구해진 치킨 거리를 합해 도시의 거리를구한다.

3. 코드

- 내 코드_Fail

n, c = map(int, input().split())
ls = [[0]*n for _ in range(n)]
for i in range(n):
    ls2 = list(map(int, input().split()))
    for j, v in enumerate(ls2):
        ls[i][j] = v
        
# 각 치킨집 리스트의 거리를 0으로 초기화
chick_ls = {} 
for i in range(n):
    for j in range(n):
        if ls[i][j] == 2:
            chick_ls[(i, j)]= 0

# 각 치킨집에서 도시의 치킨 거리를 구한다.
home_ls={}
for x, y in chick_ls.keys():
    total = 0
    for i in range(n):
        for j in range(n):
            if ls[i][j] == 1:
                home_ls[(i, j)] = 100
                total+= abs(x-i) + abs(y-j)
    chick_ls[(x, y)] = total
    
# value로 키값을 가져옴
def get_key(val):
    for key, value in chick_ls.items():
        if val == value:
            return key
        
# 도시의 치킨 거리가 가장 큰 치킨집을 폐점...거리가 같을 경우는 어떻게 할 것인가?
for _ in range(len(chick_ls)-c):
    del(chick_ls[get_key(max(chick_ls.values()))])

# 남은 치킨집 중 가장 가까운 것을 고른다.
for x, y in home_ls.keys():
    for a, b in chick_ls.keys():
        home_ls[(x, y)] = min(abs(x-a) + abs(y-b), home_ls[(x,y)])
        
answer = sum(home_ls.values())
print(answer)

해답 코드

from itertools import combinations
n, m = map(int, input().split())
chicken, house  = [],[]

for r in range(n):
    data = list(map(int, input().split()))
    for c in range(n):
        if data[c] ==1:
            house.append((r,c)) # 집 좌표
        elif data[c] == 2:
            chicken.append((r,c)) # 치킨집
            
# 모든 치킨집 중에서 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)

4. 코멘트

- 접근 방법은 비슷했던 것 같은데 해답의 경우 '조합'을 사용해서 모든 경우의 수를 다 살펴보는 방법까지 생각하지 못했다.

- 아직까지는 시간 계산이 부족해서인지, 방법을 몰라서인지 다양한 경우의 배운 내용을 접목시키지 못하고 있는 것 같다. 조금 더 다양한 경험이 필요하다.

- 분명 예전에 조합을 이용한 방법을 생각해 내기도 했었는데, 또 문제가 달라지고 상황을 제대로 정리하지 못해서 바로바로 나오지 않는 것 같다.