[Algorithm] 백준 15686- 치킨 배달 in Python(파이썬)

💡 백준 15686:

주어진 치킨 집 중 m개의 치킨집만 남기는 모든 조합에 대하여 탐색

🌱 코드 in Python

알고리즘: Brute Force

import sys
from itertools import combinations as com

input = sys.stdin.readline
n, m = map(int, input().split())
h = []
c = []
for i in range(n):
	g = list(map(int, input().split()))
	for j in range(n):
		if g[j] == 1:
			h.append((i, j)) # 집 인덱스 추가
		if g[j] == 2:
			c.append((i, j)) # 치킨 인덱스 추가

c_l = list(com(c, m)) # n개의 치킨집 중 m개를 선택하는 모든 조합
ret = 100000
for s_c in c_l: # 모든 조합의 경우를 순회하며
	tmp_ret = 0
	for s_i in h: # 해당 조합에 대해 모든 집을 순회하며
		tmp = min([abs(c_i[0] - s_i[0]) + abs(c_i[1] - s_i[1]) for c_i in s_c]) # 가장 가까운 최소 거리 탐색
		tmp_ret += tmp # 각 집의 최소 거리 합산
	ret = min(ret, tmp_ret) # 각 조합의 최소 거리 갱신
print(ret)

이번 문제 역시 조합 문제!
와 나 진짜 컴비네이션 모듈 못쓰면 어케 풀려고 그러지?
이거는 이걸 순회하는 로직을 생각하는 것보다, 조합을 만드는 게 더 어려웠던 문제가 아니었나 싶다..

🧠 기억하자

1. 최솟값 갱신
   • tmp = min([abs(c_i[0] - s_i[0]) + abs(c_i[1] - s_i[1]) for c_i in s_c])와 같이 tmp 값을 임의이 최댓값으로 상정할 필요 없이 배열에 넣고 그 중 최솟값을 뽑는 식으로 구할 수도 있다

백준 15686 바로가기