[백준] 치킨 배달 - 백준 15686 | 골드 V

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

 

 

 

문제 요약

• NxN 도시 지도에서
  • 0: 빈 칸
  • 1: 집
  • 2: 치킨집
• 이 중 M개의 치킨집만 남기고 나머지는 폐업해야 함
• 도시의 치킨 거리 = 모든 집의 "가장 가까운 치킨집 거리"의 합
• 이 치킨 거리의 최솟값을 구하는 문제

 

처음엔 완전탐색으로,,

그냥 단순하게

• 도시의 모든 치킨집 중 M개 고르고
• 각 조합마다 도시 전체 치킨 거리 계산해서
• 그 중 최솟값을 구하면 되겠다고 생각했다.

그대로 itertools.combinations()로 조합 만들고,
각 조합마다 거리 계산을 해봤다.

결과는 잘 돌아간다..  하지만 M이 13이면 조합은 10,000개 이상 나옴
중복없이 효율적으로 순회하는게 빠름

 

개선된 방식 - combinations + 최소 거리

조금 개선한 건:

• 각 집마다, 가장 가까운 치킨집 거리만 고려
• 전체 거리만 누적해서 최솟값만 비교

굳이 리스트로 다 담지 않아도 되니까 조금 더 가볍고 깔끔해짐

 

처음 풀이 :

from itertools import combinations

N, M = map(int, input().split())

city = [list(map(int, input().split())) for _ in range(N)]

house_location = []

chicken_location =[]

total_chicken_distance = 99999999

for i in range(N):

    for j in range(N):

        if city[i][j] == 1:

            house_location.append((i,j))

        if city[i][j] == 2:

            chicken_location.append((i,j))

for c in combinations(chicken_location, M):

    city_chicken_distance = []

    for house in house_location:

        distance = []

        for idx in range(M):

            distance.append(abs(house[0]-c[idx][0])+abs(house[1]-c[idx][1]))

        city_chicken_distance.append(min(distance))

    total_chicken_distance = min(total_chicken_distance,sum(city_chicken_distance))

print(total_chicken_distance)

 

 

개선된 풀이: 

 

from itertools import combinations
N, M = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(N)]
house_location = []
chicken_location = []

for i in range(N):
    for j in range(N):
        if city[i][j] == 1:
            house_location.append((i, j))
        elif city[i][j] == 2:
            chicken_location.append((i, j))
total_chicken_distance = float('inf')

for c in combinations(chicken_location, M):
    city_chicken_distance = 0
    for hx, hy in house_location:
        min_dist = float('inf')
        for cx, cy in c:
            dist = abs(hx - cx) + abs(hy - cy)
            min_dist = min(min_dist, dist)
        city_chicken_distance += min_dist
    total_chicken_distance = min(total_chicken_distance, city_chicken_distance)

print(total_chicken_distance)