python으로 푸는 백준 15686. 치킨 배달

백준 15686. 치킨 배달

사람들은 집에서 가장 가까운 거리의 치킨집을 이용한다고 한다.

집에서 가장 가까운 치킨 집과의 거리를 치킨 거리라고 한다.

주어진 치킨 집 중에서 M개만을 남기도 나머지를 폐업시키고자 할때,

모든 집에서 가장 가까운 치킨 집과의 치킨 거리의 총 합이 가장 적은

 최솟값을 출력하시오.

백준에서 푼 문제 리스트 보기

백준에서 문제 보기

github에서 코드 보기

문제 조건

치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.

도시의 치킨거리는 모든 집의 치킨 거리의 합을 말한다.

치킨 거리는 적을 수록 좋다.

모든 치킨집 중 M개를 제외한 치킨집을 폐쇄해야 한다.

문제풀이

폐쇄할 치킨집을 선택하고, 폐쇄할 치킨집에서 치킨을 시켜먹는 집들만, 폐업하지 않은 치킨집 중에 가장 가까운 치킨 거리를 구해주면 된다.

1. 필요한 값들 구해두기 (모든 치킨 집의 위치 정보, 모든 집의 위치 정보, 집마다 모든 치킨집과의 거리, 이용하는 치킨집의 고유번호)

필요한 값들을 활용하기 쉽게 저장하기 위해서 리스트(배열)와 dictionary를 이용하였다.

"모든 치킨집의 위치 정보"를 리스트에 넣는다. 각 index는 치킨집의 고유 번호가 된다.

"모든 집의 위치 정보"를 리스트에 넣는다. 각 index는 각 집을 가리키는 고유 번호가 된다.

집의 위치 정보(r,c)를 key로 하고, "집마다 모든 치킨집과의 거리"를 구한 값을 리스트(배열)에 넣은 다음에 dictionary에 값으로 넣었다.

집의 index(고유번호)를 가지고, "이용하는 치킨집의 index(고유번호)"를 리스트에 넣어준다.

이로써, 어떤 집에서 어느 치킨집을 이용할지와, 모든 치킨집과의 치킨 거리를 구해두었다. 

2. 폐쇄할 치킨집 고르기

itertools의 combinations를 활용해서 폐쇄할 치킨집을 고른다.

폐쇄할 치킨집에서 치킨을 시켜먹는 집을 찾아내서, 도시의 치킨 거리에 추가해줬던 기존 값을 빼고, 폐쇄하지 않는 치킨집 중에서 가장 최솟값인 치킨집의 치킨거리를 구해서 총 치킨 거리에 더해준다.

모든 집들을 탐색했을 때, 모든 집들이 치킨을 시킬 수 있게 되었다면  그때의 '총 치킨 거리'를 구해둔다.

그리고 모든 총 치킨 거리 중에 가장 최소 값을 반환해주면 된다.

파이썬 코드

from itertools import combinations
 
def solve(n, m, board):
    chicken_list = []
    home_list = []
    distance_dict = {}
 
    # 치킨집, 집
    for i in range(n):
        for j in range(n):
            v = board[i][j]
            if v == 2:
                chicken_list.append((i,j))
            elif v == 1:
                home_list.append((i,j))
 
    # 좋아하는 치킨집 번호 (chicken_list의 index)
    like_chicken_list = []
 
    min_total = 0
    # 집에서 치킨집과의 거리를 구한다
    for home in home_list:
        r1,c1 = home
        key = str(home)
        distances = []
        best_index = -1
        best_distance = 9999999
        for idx, chicken in enumerate(chicken_list):
            r2, c2 = chicken
            distance = abs(r1 - r2) + abs(c1 - c2)
            distances.append(distance)
            if distance < best_distance:
                best_distance = distance
                best_index = idx
        min_total += distances[best_index] # 최소 치킨 거리 저장
        like_chicken_list.append(best_index)
        distance_dict[key] = distances # 치킨집마다의 거리 정보 저장
 
    result = 99999999
    # selection : 폐점할 목록
    for selection in combinations(range(0,len(chicken_list)), len(chicken_list) - m):
        temp_min_total = min_total
 
        for idx, like in enumerate(like_chicken_list):
        # 폐점한 치킨집을 이용했던 집들을 찾아 다른 최소 치킨 거리를 구해준다.
         if like in selection:
            home = home_list[idx]
            # 다른 치킨집을 찾아야 한다.
            min_v = 99999999
 
            # 이미 구해논 치킨거리를 활용함
            distances = distance_dict[str(home)]
            for i, distance in enumerate(distances):
                # 내가 구매하는 치킨 집이었다면 치킨거리를 빼주고(리셋)
                if i  == like:
                    temp_min_total -= distance
                    # 빼야한다
                elif i not in selection:
                    if min_v > distance:
                        min_v = distance
            # 다시 계산한 값
            temp_min_total += min_v
        if temp_min_total < result:
            result = temp_min_total
    print(result)
    return result
 
 
if __name__ == "__main__":
    n, m = map(int, input().strip().split())
    board = []
    for i in range(n):
        line = list(map(int, input().strip().split()))
        board.append(line)
    solve(n, m, board)

#백준 15686. 치킨 배달 #백준 15686 파이썬 #파이썬 백준 15686. 치킨 배달 #15686. 치킨 배달 Python