치킨 배달

m개의 치킨집을 골라낸 후, 각 집의 치킨 거리합을 구한다. 이때, m개의 치킨집을 고른 경우들 중, 가장 작은 도시의 치킨 거리를 구하는 문제이다.

집과 치킨집의 좌표들을 ‘house’와 ‘chicken’에 dictonary를 이용해 저장했다. 탐색하며 나오는 첫 번째 집의 좌표를 house[0]에 입력하고, 두 번째 집의 좌표를 house[1]에 입력하는 식으로 저장했다. 치킨집도 마찬가지이다. m개의 chicken집을 추릴 때, index만 사용해서 조금 더 간단하게 DFS를 진행하기 위해 이 방식을 사용해 저장했다. (combination을 사용할 수도 있지만, DFS를 이용해 풀었다.) 이 과정은 평범한 DFS임으로, 밑의 코드를 참고하면 쉽게 이해할 수 있을 것이다.

이제, 골라진 m개의 치킨집에 대해서 도시의 치킨 거리를 구해야한다.

def DIST(chicken_list):
    dist_sum = 0

    for j in range(cnt_house+1):
        a, b = house[j]
        dist = sys.maxsize
        for i in chicken_list:
            x, y = chicken[i]
            dist = min(dist, abs(x-a)+abs(y-b))
        dist_sum += dist

    return dist_sum

DFS를 수행해서 얻은 m개 치킨집의 리스트를 인자로 받았다. 각각의 집에 대해 초기 치킨 거리를 파이썬의 정수형 최대값으로 설정해준다. 모든 치킨집에 대해 x축, y축 좌표값을 비교해 거리를 구하고, 이 거리들의 최소값을 ‘dist_sum’에 더해주었다.

모든 집의 치킨거리를 더한 ‘dist_sum’이 최종적으로 도시의 치킨 거리가 된다.

이 ‘dist_sum’들의 최소값을 찾아 출력하자.


CODE

from collections import deque
import sys
read = sys.stdin.readline
answer = sys.maxsize

n, m = map(int, read().split())
MAP = list(list(map(int, read().split())) for _ in range(n))

# 치킨집과 집들의 좌표 저장
chicken = dict()
house = dict()
# dictionary에 치킨집과 집들을 0번부터 번호를 매기기 위해 사용
cnt_chicken = -1
cnt_house = -1

for i in range(n):
    for j in range(n):
        if MAP[i][j] == 2:
            cnt_chicken += 1
            chicken[cnt_chicken] = (i, j)
        if MAP[i][j] == 1:
            cnt_house += 1
            house[cnt_house] = (i, j)

# 치킨집을 m개만큼 골라낸후, 치킨거리의 최소값을 answer에 저장한다.
def DFS(chicken_list, index, count):
    global answer
    if count == m:
        answer = min(answer, DIST(chicken_list))
    else:
        for i in range(index, cnt_chicken+1):
            DFS(chicken_list+[i], i+1, count+1)

# 골라진 m개의 치킨집에 대해 각각의 집들로 부터의 치킨 거리를 구한다.
def DIST(chicken_list):
    dist_sum = 0

    for j in range(cnt_house+1):
        a, b = house[j]
        dist = sys.maxsize
        for i in chicken_list:
            x, y = chicken[i]
            dist = min(dist, abs(x-a)+abs(y-b))
        dist_sum += dist

    return dist_sum

DFS([], 0, 0)
print(answer)


틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]