문제

많이 익숙한 문제였다. 엘리스에서도 멘토님께서 언급한 적도 있고, 느낌도 기업 코테 냄새가 솔솔 나는 구현 문제!
많이 회자되는만큼 중요하다는 의미겠지

풀이 전 생각했던 방향

2차원 그래프하면 이제 DFS / BFS밖에 생각이 안 나서 처음에는 집으로부터 최소 거리인 치킨집을 찾을 때 그래프 돌리는 것을 해볼까 싶었지만 왠지 쎄한 느낌이 나서 다른 방향을 생각해보았다.

그래서 완전탐색으로 풀다가 조합을 써야겠다는 생각을 하자마자 시간 초과가 걱정이 되었는데, 치킨 집의 개수의 제한이 13개인 것을 보고, 대충 할 만 하지 않을까하는 생각이 들어 냅다 풀기 시작했는데 왠걸 수월하게 맞았다!

풀이

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

citySize, limitCH = map(int, input().split())

chickenDistanceInfo = {}
chickenInfo = []
houseInfo = []

for i in range(1, citySize+1):
    rowInfo = list(map(int, input().split()))
    for colIndex in range(1, citySize+1):
        if rowInfo[colIndex-1] == 1:
            houseInfo.append((i, colIndex))
        elif rowInfo[colIndex-1] == 2:
            chickenInfo.append((i, colIndex))

# make chickenDistance
for chickenZip in chickenInfo:
    cR, cC = chickenZip
    chickenDistanceInfo[chickenZip] = []
    for house in houseInfo:
        hR, hC = house
        chickenDistance = abs(cR-hR) + abs(cC-hC)
        chickenDistanceInfo[chickenZip].append(chickenDistance)

# erase 
# print(chickenDistanceInfo)
# 행은 치킨집, 열은 일반집
# {      (1, 3)(2, 5)(3, 2)(4, 3)
# (2, 3): [1,    2,    2,    2], 
# (3, 3): [2,    3,    1,    1], 
# (5, 5): [6,    3,    5,    3]}

def calculateChickenDistance(info):
    totalDistance = 0
    for i in range([len(value) for key, value in info.items()][0]):
        minDistanceEachHouse = float('inf')
        for key, value in info.items():
            if value[i] < minDistanceEachHouse:
                minDistanceEachHouse = value[i]
        totalDistance += minDistanceEachHouse
    return totalDistance

if len(chickenDistanceInfo) == limitCH:
    print(calculateChickenDistance(chickenDistanceInfo))
else:
    minChickenDistance = float('inf')
    # a b c d e 2 5C2
    for selectedChickenHouses in combinations(chickenInfo, limitCH):
        selectedChickenInfo = {}
        for chickenHouse in selectedChickenHouses:
            selectedChickenInfo[chickenHouse] = chickenDistanceInfo[chickenHouse]
        tempMinValue = calculateChickenDistance(selectedChickenInfo)
        if tempMinValue < minChickenDistance:
            minChickenDistance = tempMinValue
    print(minChickenDistance)

1. 치킨집의 좌표와 일반집의 좌표를 따로 저장한다.
2. 치킨집을 기준으로 각각 일반집에 해당하는 치킨거리를 dictionary에 저장한다.
   3-1. 현재 치킨집이 남아 있어야 하는 치킨집 수만큼 존재한다면 바로 치킨거리를 계산한다.
   3-2. 현재 치킨집이 남아 있어야 하는 치킨집 수보다 크다면 (현재치킨집)Combination(남아 있어야 하는 치킨집)을 하면서 최소 치킨 거리를 갱신한다.