[백준 - 15686] 치킨배달

문제

문제링크
존재하는 치킨집 중 정해진 수만큼만 남기고 폐업을 할 것이다. 모든 집에 대한 치킨집의 거리의 합이 최소한이 되도록 하시오.

치킨의 거리 = 가장 가까운 치킨집과의 거리
도시의 치킨의 거리 = 모든 집의 치킨의 거리의 합

문제 풀이

치킨의 거리와 도시의 치킨의 거리에 대해 이해하는데 조금 걸렸다.
하지만 이번에는 조건 범위를 보고 모든 조합에 대해 접근한다고 하면 경우의 수는 13Cm이므로 가능하겠다고 생각했다.

# 나의 작성코드

from itertools import combinations

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

array = [[0] * ( n + 1 )]
chicken = []
home = []
for row in range(1, n+1):
    array.append([0] + list(map(int, input().split())))
    for col, temp in enumerate(array[row]):
        if temp == 2:
            chicken.append((row, col))
        elif temp == 1:
            home.append((row, col))


answer = 987654321

for selected in combinations(range(len(chicken)), m):
    # 선택된 인덱스의 치킨집 거리를 체크
    city = 0
    for h_x, h_y in home:
        # 각 집에서 선택된 치킨집 까지의 거리를 측정
        street = 987654321
        for idx in selected:
           c_x, c_y = chicken[idx]
           street = min(street, abs(h_x - c_x) + abs(h_y - c_y))
        city += street
    answer = min([answer, city])

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(candidiate):
    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)

개선할 점

• combinations 내 list를 넣고 숫자를 넣어주면 조합에 맞게 그 요소들을 담아서 보내준다.
• 아직까지는 C++ 방식이 보이는 코드를 짜는 것 같다.

해당 문서는 '이것이 코딩 테스트다 with 파이썬 - 나동빈 저'를 공부하며 정리한 글입니다.