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

15686번: 치킨 배달

문제

 

"치킨거리"값이 가장 큰 값이 되도록 폐업시킬 치킨집을 적절히 고르는 문제이다.

---

 

아이디어

N값이 최대 50이고 시간제한은 1초이기 때문에 n3으로 모든 경우를 탐색해도 시간에 걸리지 않는다고 생각했다.
따라서 브루투포스로 문제를 해결하였다.

---

풀이

N, M = map(int, input().split())
city = list(list(map(int, input().split())) for _ in range(N))
result = sys.maxsize

home = []
chicken = []

for i in range(N):
  for j in range(N):
    if city[i][j] == 1:
      home.append([i, j])
    
    elif city[i][j] == 2:
      chicken.append([i, j])

 

집과 치킨집의 정보가 있는 도시를 입력받아준다.

이후 집과 치킨집의 좌표를 따로 배열에 입력해주었다.

 

 

for chi in combinations(chicken, M):
  tmp = 0
  for h in home:
    chickenLength = sys.maxsize
    for j in range(M): #집 하나와 뽑은치킨집을 비교하며 가장 가까운 거리 계산
      chickenLength = min(chickenLength, abs(h[0] - chi[j][0]) + abs(h[1] - chi[j][1]))
    tmp += chickenLength #치킨거리를 계산

  result = min(result, tmp)

3중 for문을 사용해서 모든 경우를 탐색하였다.

이 문제의 경우 폐업시키지 않을 치킨집을 골라야하기 때문에 파이썬의 combination을 사용하였다.

combination을 사용할 경우 배열에서 M개를 뽑는 경우의 수를 모두 구할 수 있다.

 

뽑은 치킨집을 하나씩 집과 비교하여 집과 가장 가까운 치킨집을 골라 tmp에 넣어주었다.

최종적으로 tmp값은 M개의 치킨집을 골랐을 때 치킨거리가 된다.

 

이후 tmp값과 result값을 비교하여 둘 중 작은 값을 result에 할당한다.

최종적으로 result를 출력하면 가장 작은 치킨거리가 된다.

 

---

코드

import sys
from itertools import combinations
N, M = map(int, input().split())
city = list(list(map(int, input().split())) for _ in range(N))
result = sys.maxsize

home = []
chicken = []

for i in range(N):
  for j in range(N):
    if city[i][j] == 1:
      home.append([i, j])
    
    elif city[i][j] == 2:
      chicken.append([i, j])


for chi in combinations(chicken, M):
  tmp = 0
  for h in home:
    chickenLength = sys.maxsize
    for j in range(M): #집 하나와 뽑은치킨집을 비교하며 가장 가까운 거리 계산
      chickenLength = min(chickenLength, abs(h[0] - chi[j][0]) + abs(h[1] - chi[j][1]))
    tmp += chickenLength #치킨거리를 계산

  result = min(result, tmp)

print(result)