백준 알고리즘 15686번 치킨 배달 풀이 With Python

문제 링크: https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

이 문제는 크게 2가지 문제를 해결해야 합니다. 첫 번째 문제는 치킨 집중에 m개의 치킨집을 선택해야 하는 조합 문제입니다. 두 번째 문제는 각 집을 치킨집과의 거리를 계산하여 최솟값을 구하는 문제입니다. 2가지를 해결하면 되는 문제로 소스코드는 아래와 같습니다. 저는 itertools 라이브러리에서 combinations를 가져오지 않고 직접 구현하는 연습을 하여 combinations 함수를 가져와서 사용했을 때보다 시간이 조금 더 걸렸습니다. 

# 조합 구현
def combination(arr, r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for next in combination(arr[i + 1:], r - 1):
                yield next + [arr[i]]


n, m = map(int, input().split())
answer = float('inf')
chicken = []
house = []
# 집과 치킨집의 좌표를 house와 chicken에 저장합니다.
for i in range(n):
    s = list(map(int, input().split()))
    for j in range(n):
        if s[j] == 1:
            house.append((i, j))
        elif s[j] == 2:
            chicken.append((i, j))
# 치킨집 중에 m개를 뽑아서 거리를 측정합니다.
for case in combination(chicken, m):
    sub = 0
    for h in house:
        mini = float('inf')
        for c in case:
            if mini > abs(h[0] - c[0]) + abs(h[1] - c[1]):
                mini = abs(h[0] - c[0]) + abs(h[1] - c[1])
        sub += mini
    if answer > sub:
        answer = sub
print(answer)

소스코드에 대한 질문이 있으시면 댓글 남겨주시면 답변드리겠습니다. 읽어주셔서 감사합니다. : - )