[백준] 15686번: 치킨 배달 - 파이썬

문제출처

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

15686번: 치킨 배달

 

 

 

---

 

풀이 및 코드

요즘 그래프 문제를 너무 많이 풀었나 보다... 그리 어려운 문제가 아니라고 생각하면서 가게와 집 사이의 거리를 bfs로 접근하려고 했다. 그렇게 구현을 하다보니 시간이 너무 오래 걸렸고 코드를 작성하다가 이상함을 느껴 다른 방법을 고민해 보았다. 우리에겐 combination 매서드가 있다! 그냥 가게 m개를 조합으로 골라서 가장 작은 치킨 거리 값을 출력하면 된다. 하... 난 왜 이리 오래 고민했는가...

 

 

 

	from itertools import combinations
	# 데이터 전처리
	n,m = map(int, input().split())
	city = [list(map(int, input().split())) for _ in range(n)]
	houses = [] # 집들의 좌표(r,c) 배열로 저장
	stores = [] # 치킨 가게들의 좌표(r,c) 배열로 저장
	for r in range(n):
	for c in range(n):
	if city[r][c] == 1:
	houses.append((r,c))
	elif city[r][c] == 2:
	stores.append((r,c))
	# 치킨 거리 찾기 함수
	def chicken_dist(houses, stores):
	dist = 0
	for r, c in houses:
	dist += min(abs(r-ch_r) + abs(c-ch_c) for ch_r, ch_c in stores)
	return dist
	# 조합 함수를 사용해 골라진 m개의 가게에 대한 치킨 거리를 계산해 작은 값 찾기
	answer = float("inf")
	for selected in combinations(stores, m):
	answer = min(answer, chicken_dist(houses, selected))
	print(answer)

view raw 14686.py hosted with ❤ by GitHub