[Python] 백준 15686. 치킨 배달

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

15686번: 치킨 배달

삼성SW역량테스트 기출문제. Brute Force + BFS 형태.

치킨집 중에 M개를 고르는 형태는 '연구소 3' 문제와 마찬가지로 combinations 라이브러리를 써서 해결할 수 있다.

 

 

	import sys
	import math
	from itertools import combinations
	n, m = map(int, sys.stdin.readline().split())
	# 치킨집 위치, 집 위치
	chicken, house = [], []
	# 치킨집 위치 / 집 위치 저장
	for y in range(n):
	tmp = list(map(int, sys.stdin.readline().split()))
	for x in range(len(tmp)):
	if tmp[x] == 1:
	house.append((y,x))
	elif tmp[x] == 2:
	chicken.append((y,x))
	# 치킨집 중 m개의 치킨집을 선택하는 경우의 수
	candidate = list(combinations(chicken, m))
	# 거리 최소값 구하기.
	# 각 집 위치마다 모든 치킨집과의 거리를 구하고, 최솟값만 result에 더한다.
	def get_min_distance(candidate, house):
	result = 0
	for hy, hx in house:
	tmp_min = math.inf
	for y, x in candidate:
	if abs(hy-y) + abs(hx-x) < tmp_min:
	tmp_min = abs(hy-y)+ abs(hx-x)
	result += tmp_min
	return result
	# 거리의 최솟값
	min_result = math.inf
	for i in candidate:
	result = get_min_distance(list(i),house)
	if min_result > result:
	min_result = result
	print(min_result)

view raw [백준] 치킨 배달.py hosted with ❤ by GitHub