[ BOJ / 파이썬 ] 15686 치킨 배달

 

/  첫 제출  /

 

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

city = [list(map(int, input().split())) for _ in range(n)]
chickens = []
homes = []
for x in range(n):
  for y in range(n):
    if city[x][y] == 2:
      chickens.append([x, y])
    if city[x][y] == 1:
      homes.append([x, y])
      
chickenDist = []
for store in chickens:
  i = 0
  dist = 0
  for home in homes:
    dist += abs(store[0] - home[0]) + abs(store[1] - home[1])
  chickenDist.append([store, dist])
  
chickenDist.sort(key = lambda x : x[1])
shopList = chickenDist[:m]

result = 0
for home in homes:
  dist = n*n
  for shop in shopList:
    newDist = abs(shop[0][0] - home[0]) + abs(shop[0][1] - home[1])
    dist = min(dist, newDist)
  result += dist
print(result)

 

첫 번 째 제출에서는 문제 상 나와 있는 테스트케이스는 다 맞았는데, 제출하니 바로 1초컷 당했다. 왜..? ㅠ

오늘 5문제째라서 더이상 코드 들여다볼 자신이 없어 질문검색방 갔는데, 첫 글이 이 내용이었다.

이 문제는 그리디 알고리즘으로 풀 수 없습니다. 즉 1개만 남기는 경우의 최선의 선택이 2개만 남기는 경우의 최선의 선택 안에 포함되리라는 보장은 없습니다.아래의 반례에서, 하나만 남긴다면 정중앙의 지점을 남겨야 하겠습니다. 즉 5 1 로 돌렸을 때는 답이 12가 나옵니다.하지만 지점을 4개 남기는 경우의 해답은 각 모서리의 지점들을 남기는 것으로, 답은 4가 나와야 합니다. 이때는 정중앙의 지점을 남기면 안 됩니다.
5 1
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
ans: 12

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
ans: 4

딱 위에것만 맞고 아래거는 틀리는 느낌

 

ㅡ 

그래서 도시 지도도 범위가 작고 해서 조합으로 모든 후보군 구해서 풀었다. 

 

/  두번째 제출  /

import sys
from itertools import combinations
input = sys.stdin.readline

n, m = map(int, input().split())

city = [list(map(int, input().split())) for _ in range(n)]
chickens = []
homes = []
for x in range(n):
  for y in range(n):
    if city[x][y] == 2:
      chickens.append([x, y])
    if city[x][y] == 1:
      homes.append([x, y])


shopList = combinations(chickens, m)

result = 1e9
for shops in shopList:
  dist = 0
  for home in homes:
    minChicken = n*n
    for shop in shops:
      eachDist = abs(shop[0] - home[0]) + abs(shop[1] - home[1])
      minChicken = min(minChicken, eachDist)
    dist += minChicken
  result = min(result,dist)
print(result)