(Python) 백준 15686번: 치킨 배달

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

15686번: 치킨 배달

 

# Code

from itertools import combinations
 
## 맵크기(N), 치킨집 최대 선택가능개수(M)
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
 
## 빈칸(0), 집(1), 치킨집(2)
house = []
chicken = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 1: house.append((i, j))
        elif board[i][j] == 2: chicken.append((i, j))
 
minv = float('inf')
for ch in combinations(chicken, M):
    sumv = 0
    for home in house:
        sumv += min([abs(home[0]-i[0])+abs(home[1]-i[1]) for i in ch])
        if minv <= sumv: break
    if sumv < minv: minv = sumv
 
print(minv)

---

 

(Python) 백준 15686번: 치킨 배달¶

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

---

In [33]:

from itertools import combinations

In [34]:

## 입력값 받기
## 맵크기(N), 치킨집 최대 선택가능개수(M)
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]

5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2

잘 입력받았는지 확인

In [36]:

print(N, M)

for i in range(N):
    print(board[i])

5 3
[0, 0, 1, 0, 0]
[0, 0, 2, 0, 1]
[0, 1, 2, 0, 0]
[0, 0, 1, 0, 0]
[0, 0, 0, 0, 2]

집과 치킨집에 대한 위치 정보를 저장하자.

In [37]:

## 빈칸(0), 집(1), 치킨집(2)
house = []
chicken = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 1: house.append((i, j))
        elif board[i][j] == 2: chicken.append((i, j))

In [38]:

house # 집 위치

Out[38]:

[(0, 2), (1, 4), (2, 1), (3, 2)]

In [39]:

chicken # 치킨 집 위치

Out[39]:

[(1, 2), (2, 2), (4, 4)]

최대 M개의 치킨집을 고를 수 있다고 문제에 명시되어 있다.

선택된 치킨집이 많으면 많을수록 거리가 최소가 될 가능성이 크다.

즉, 전체 치킨집 중에서 M개를 선택하되, 그 중에서 거리가 가장 최소가 되는 곳으로 골라야 한다.

In [40]:

minv = float('inf')

In [41]:

for ch in combinations(chicken, M):
    sumv = 0
    for home in house:
        sumv += min([abs(home[0]-i[0])+abs(home[1]-i[1]) for i in ch])
        if minv <= sumv: break
    if sumv < minv: minv = sumv

In [42]:

print(minv)

5