[백준] 15686. 치킨 배달 (python)

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

from itertools import combinations
n, m = map(int, input().split())
INF = int(1e9)
city = [[0]*(n+1) for _ in range(n+1)]

# (1,1)부터 시작
# 집, 치킨집 정보 저장
house = []
chicken = []
for i in range(n):
    data = list(map(int, input().split()))
    for j in range(len(data)):
        if data[j] == 1:
            house.append([i+1, j+1])
        elif data[j] == 2:
            chicken.append([i+1,j+1])

# 치킨 거리 구하기
def chicken_distance(house, chicken):
    total_chicken = 0
    for h in house:
        min_number = INF
        for c in chicken:
            distance = abs(c[0] - h[0]) + abs(c[1] - h[1])
            min_number = min(min_number, distance)
        total_chicken += min_number
    return total_chicken

total_chicken = INF                 # 도시의 치킨거리
save_chicken = list(combinations(chicken, m))  # 최대 m개의 치킨집을 고르기
for sc in save_chicken:
    total_chicken = min(total_chicken, chicken_distance(house, sc))

print(total_chicken)

 

1. 집과 치킨집 정보를 각각 리스트에 저장한다.

2. 도시의 치킨 거리를 구하는 함수를 만든다.

    각 집 리스트의 원소와 치킨 리스트의 원소를 돌면서 각각 거리를 구해 최솟값을 구한다. -> 각 집의 치킨 거리

    구해지는 치킨 거리를 모두 더해 도시의 치킨 거리를 반환한다.

3. 최대 m 개의 치킨집을 남길 예정이기 때문에

    현재 있는 치킨집 중에서 m개를 고르는 조합 리스트를 만든다.

4. 살아남는 치킨 조합 리스트를 순회하면서 각각 도시의 치킨 거리르 구해 그 중 가장 작은 값을 저장해 출력한다.

 

 

처음 풀이때에는 살아남는 치킨 조합이 아니라 삭제할 치킨 조합을 구해서

치킨집 리스트에서 삭제할 치킨 조합을 삭제한 뒤에 도시의 치킨 거리를 구하고

다시 치킨집 리스트에 똑같은 조합을 추가하여 원상복구시킨다음에

다음 조합을 삭제한 뒤에 도시의 치킨 거리를 구하는 것을 반복하면서 도시의 치킨 거리를 구했다.

이렇게 했을 때 정답이긴 했지만 시간이 너무 오래걸려서 수정할 필요가 있다고 생각했다.

그래서 폐업시키지 않을 치킨집 리스트를 구해서 도시 치킨 거리의 최솟값을 구하는 방식을 변경했다.

 

변경 전

total_chicken = INF                 # 도시의 치킨거리
remove_cnt = len(chicken) - m       # 폐업시킬 치킨집의 최소 개수
min_chicken_cnt = len(chicken) - 1  # 폐업시킬 치킨집의 최대 개수

for remove in range(remove_cnt, len(chicken)):
    r = list(combinations(chicken, remove))
    for remove_combi in r:
        for index in range(remove):
            chicken.remove(remove_combi[index])
        total_chicken = min(total_chicken, chicken_distance(house, chicken))
        for index in range(remove):
            chicken.append(remove_combi[index])

print(total_chicken)