15686: 치킨 배달

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

설명

기존에 있는 치킨집의 수를 줄여서 최대 M개로 유지한다. 그 상태에서 일반집들로부터 M개의 치킨 집까지의 거리를 줄이는 것이 목표이다. 이후에 도시의 치킨 거리 합의 최솟값을 계산하는 문제다. 

핵심 아이디어

우선, 치킨집의 개수 범위는  M <= 치킨 집의 개수 <= 13 이다. 만약에 치킨 집 중에서 M개를 고르는 모든 경우의 수를 고려하면 최대 13개에서 M를 고르는 조합과 동일하다. 이 경우 M이 어떤 값이 되는지 간에 13CombinationM의 값은 100,000을 넘지 않는다. 집의 개수 또한 100개 이므로, 모든 경우의 수를 다 계산해도 시간초과 없이 해결 가능.

• 파이썬의 조합 라이브러리 활용. -> from itertools import combinations
• 치킨집 중에서 M개를 고르는 모든 경우에 대해서 치킨 거리의 합을 계산하고 (완전 탐색), 치킨 거리의 최솟값을 구해 출력하면 된다. 

candidates = combinations(chicken,m)

이렇게 하면 튜플로 반환하기 때문에 list로 감싸서 리스트 형태로 반환한다.

# 조합을 튜플 형태로 반환해서 리스트로 변환해서 할당
candidates = list(combinations(chicken, m))

순열과 조합

순열: permutation

순열이란 서로다른 n개 중에서 순서를 고려하여 나열한 경우의 수를 의미한다. 즉, 서로 다른 n 개중 r개를 골라 순서를 정해 나열하는 가짓 수를 의미한다. 따라서 순서를 고려하기 때문에 (A,B)와 (B,A)는 서로 다른 것!

from itertools import permutations

arr = ['A', 'B', 'C']
nPr = permutations(arr, 2)
print(nPr) # <itertools.permutations object at 0x000001982A750D10>
print(list(nPr))
# [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

조합: combination

조합이란 서로 다른 n개 중에서 순서를 고려하지 않고 나열한 경우의 수를 의미한다. 즉, 서로 다른 n개 중에서 r개를 골라 순서를 고려하지 않고 나열하는 가짓 수를 의미한다. 따라서 순서를 고려하지 않기 때문에 (A,B)와 (B,A)는 같은 것이다.

from itertools import combinations
nCr = combinations(arr,2)
print(list(nCr))
# [('A', 'B'), ('A', 'C'), ('B', 'C')]

코드 구현

# 치킨거리: 집과 가장 가까운 치킨집 사이의 거리
# 집을 기준으로 정해진다.
# 도시의 치킨 거리: 모든 집의 치킨 거리
# 따라서 도시의 치킨 거리가 최소가 되는 값을 구해야함.

from itertools import combinations
# 맵의 크기 입력받기
n, m = map(int, input().split())
# 거리 계산을 위해 집과 치킨 집 좌표를 따로 배열로 관리
house = []
chicken = []
# 맵 정보 입력받기
graph = []
for i in range(n):
	data = list(map(int, input().split()))
	for j in range(n):
		if data[j] == 1: # 일반 집
			house.append((i,j))
		elif data[j] == 2: # 치킨 집
			chicken.append((i,j))
# print(house)
# print(chicken)
# 도시에 있는 치킨집 중에서 M개를 고르는 모든 조합을 선택
candidates = list(combinations(chicken, m))
#print(candidates)
# 치킨 거리의 합을 구하는 함수 정의
def get_sum(candidate):
	# 치킨 거리의 합을 저장하는 변수
	result = 0
	# 모든 집에 대하여
	for hx, hy in house:
		temp = 1e9 # 가장 가까운 치킨집을 찾기
		for cx, cy in candidate:
			temp = min(temp, abs(hx-cx) + abs(hy-cy))
		result += temp
	return result # 치킨 거리의 합 반환

# 도시의 치킨 거리의 최솟값을 출력
ans = 1e9
for candidate in candidates:
	ans = min(ans, get_sum(candidate))
print(ans)