[백준/Python] 15686번 치킨 배달

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

15686번: 치킨 배달

 

문제분석

1. 분류
   • 구현, 브루트포스 알고리즘, 백트래킹
2. 문제설명
   • 크기가 NxN인 도시가 있고, 도시는 1x1 크기의 칸으로 나누어져 있다.
   • 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다.
   • 도시의 칸은 (r, c)와 같은 형태로 나타나고, r과 c는 1부터 시작한다.
   • 치킨 거리: 집과 가장 가까운 치킨집 사이의 거리 → (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|
   • 도시의 치킨 거리는 모든 집의 치킨 거리의 합
   • 도시에 있는 치킨집 중에서 최대 M개를 고르고, 어떻게 고르면 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성한다.

 

코드

1	from itertools import combinations
2
3	n, m = map(int, input().split())
4	city = list(list(map(int, input().split())) for _ in range(n))
5	result = 999999
6	house = []      # 집의 좌표
7	chicken = []      # 치킨집의 좌표
8
9	for i in range(n):
10	for j in range(n):
11	if city[i][j] == 1:
12	house.append([i, j])
13	elif city[i][j] == 2:
14	chicken.append([i, j])
15
16	for c in combinations(chicken, m):  # m개의 치킨집 선택
17	temp = 0            # 도시의 치킨 거리
18	for h in house:
19	distance = 999   # 각 집마다 치킨 거리
20	for j in range(m):
21	distance = min(distance, abs(h[0] - c[j][0]) + abs(h[1] - c[j][1]))
22	temp += distance
23	result = min(result, temp)
24
25	print(result)

 

문제풀이

• m개의 치킨집을 선택하는 모든 조합에 대해 도시의 치킨 거리를 구한다.
• 치킨 거리 : abs(r1-r2) + abs(c1-c2)
• 집과 치킨집의 좌표를 각각 리스트에 저장
•  itertools의 combinations를 이용하여 치킨집 리스트 chicken에서 m개를 선택하고 치킨 거리를 구한다.