문제

치킨 배달 거리의 최소값을 구하는 것이다. 치킨집의 개수는 문제에서 정해줌

📌 코드

import sys
from itertools import combinations

sys.stdin = open('BOJ15686.txt')

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


chicken = []
home = []
minv = 999999999999999999999

for r in range(N):
    for c in range(N):
        if road[r][c]==2:
            chicken.append((r,c))
        elif road[r][c]==1:
            home.append((r,c))

for ch in combinations(chicken,M):
    sumv = 0
    for h in home:
        sumv += min([abs(h[0] - i[0]) + abs(h[1] - i[1]) for i in ch])
        if minv <= sumv :break
    if sumv < minv :
        minv = sumv


print(minv)
# print(home)

🙄 문제 풀 때 어떤 생각을 했나요?

일단 chicken과 home의 위치 좌표를 각각 저장해야겠다.
그리고 문제에서 정의해준 치킨 집의 개수 (M) 에 맞춰서 치킨집의 조합을 짜야겠다.
그리고 조합별로 home과의 거리를 구해서 최소값이 되는 경우를 찾아야겠다.

나름 훌륭한 접근인거 같았어요.
그런데 저는 치킨집의 조합 을 dfs로 짜려고 했거든요? 그런데 시간초과가 났어요.
그래서 파이썬의 from itertools import combinations 를 활용해서 조합의 종류를 만들어 놓고 집과 최소거리를 찾았습니다.