백준 15686번 치킨 배달

백준 15686번 치킨 배달

문제 바로가기

코드

import sys
from itertools import combinations

def minimumChickenDistance():
  chicken_comb = list(combinations(chickens, M))
  answer = float('inf')
  for selected_chickens in chicken_comb:
    dist_sum = 0
    chicken_dist = [[0 for _ in range(N)] for _ in range(N)]
    for chicken in selected_chickens:
      chicken_r, chicken_c = chicken
      for house_r, house_c in house:
        dist = abs(chicken_r - house_r) + abs(chicken_c - house_c)
        if chicken_dist[house_r][house_c] == 0:
          dist_sum += dist
          chicken_dist[house_r][house_c] = dist
        elif chicken_dist[house_r][house_c] > dist:
          dist_sum -= chicken_dist[house_r][house_c]
          dist_sum += dist
          chicken_dist[house_r][house_c] = dist
    answer = min(answer, dist_sum)  

  return answer

N, M = map(int, sys.stdin.readline().split())
town = [[0 for _ in range(N)] for _ in range(N)]

chickens = []
house = []

for r in range(N):
  li = list(map(int, sys.stdin.readline().split()))
  for c in range(N):  
    if li[c] == 1:
      town[r][c] = 1
      house.append((r, c))
    elif li[c] == 2:
      town[r][c] = 2
      chickens.append((r, c))

print(minimumChickenDistance())

문제 해결

❌ 우선순위 큐를 활용한 거리의 누적합

처음에는 최소거리에 사용될 치킨집을 먼저고르는 작업을 했었습니다.
따라서 각 치킨집의 좌표를 구하고 반복문을 통해서 집에서 각 치킨집까지의 거리의 누적합을 구하고 우선순위 큐를 활용하여 가장 적은 거리를 가진 치킨집만 활용하도록 했습니다.

for chicken_r, chicken_c in chicken:
  dist = 0
  for house_r, house_c in house:
    dist += abs(chicken_r - house_r) + abs(chicken_c - house_c)
  heappush(queue, [dist, chicken_r, chicken_c])

for i in range(M):
  dist, chicken_r, chicken_c = heappop(queue)
  for house_r, house_c in house:
    dist = abs(chicken_r - house_r) + abs(chicken_c - house_c)
    chicken_dist[house_r][house_c] = min(chicken_dist[house_r][house_c], dist)

그러나..

누적합으로 치킨집을 고르게 된다면

5 4
2 1 0 1 2
0 0 0 0 0
0 0 2 0 0
0 0 0 0 0
2 1 0 1 2

다음과 같은 반례에 막히게 됩니다.

⭕️ 조합을 활용한 탐색방법

chicken_comb = list(combinations(chickens, M))

결국 어느 치킨집을 고르는가에 따라서 각 거리의 합이 계속 달라지기 때문에 모든 경우의 수를 탐색하고 최솟값을 탐색하기로 했습니다.

따라서 조합을 이용해서 주어진 남겨야할 치킨집 개수를 이용하여 가능한 조합 경우의 수를 구했습니다. 이때 파이썬 기본 라이브러리인 itertools 의 combinations을 활용했습니다.

from itertools import combinations

모든 경우의 수를 탐색하며 최솟값을 찾은 결과.. 정답!!