알고리즘 - Python / 백준 - 15686번 : 치킨 배달

15686번: 치킨 배달 (acmicpc.net)

15686번: 치킨 배달

 

---

풀이

• 정사각형 2차원 배열에 치킨집과 집의 위치가 주어지고 , m개의 치킨집만 남긴다고 할 때 , 집과 가장 가까운 치킨집의 거리가 가장 적게 나오는 경우의 치킨집과 집들 사이의 거리의 합을 출력하는 문제다.
• 한 줄에 문제를 표현하기 어려워 길게 썼으니 , 위의 문제 사이트에 가서 문제를 읽어보는 것을 추천한다.
• 일단 문제를 딱 보았을 때 , 2차원 배열 그래프 탐색 문제인가 하였으나 , 천천히 읽어보니 아예 관계가 없었다.
• 우선 치킨집을 m개만 살릴 텐데 , m은 1 ~ 13이고 치킨집의 개수는 m ~ 13이다.
• 즉 최대 치킨집의 수는 13개 이고 , 이중 살릴 치킨집을 m개 고르는 것이다.
• 살릴 치킨집 조합은 조합(C)와 관련된 부분이므로 최대 13C6 즉 1716개의 조합이 나오게 된다.
• N이 최대 50이므로 50 * 50 배열 (2500) 개의 판에서 치킨집이 최대 13개 이므로 집은 최대 2487개 존재할 수 있다.
• 그렇다면 최대 2487개의 집에서 치킨집이 m개 살린다고 하였을 때 계산해야 하는 거리의 횟수는 2487 * m이고 이러한 조합이 최대 1716개 존재할 수 있으므로 대략적인 계산을 해보면  4,267,692 * m 번 연산을 한다.
• 위의 조합의 수가 1716인 경우 m = 6 이므로 약 2500만 번의 연산을 하면 찾을 수 있다는 결론이 나온다.
• 대략적인 문제의 감을 잡기 위해 계산한 부분으로 최악의 케이스가 아닐 수 있지만 , 일단 전수조사 풀이로 생각을 하고 조합을 활용하여 풀기로 가닥을 잡았다.
• 알고리즘 문제풀이의 경우 파이썬은 대략 1초 = 2000만으로 잡고 푸니 , PyPy3로는 여유 있을 거라 생각했다.
• 틀렸다면 , 최적화를 위한 다른 방법을 생각했겠지만 , 정답이 나왔다. 

 

import sys
from itertools import combinations
n,m = map(int, sys.stdin.readline().split(" "))
c = []
for _ in range(n):
    c.append(list(map(int , sys.stdin.readline().split(" "))))
house = []
chick = []
for i in range(n):
    for t in range(n):
        if c[i][t] == 1:
            house.append([i,t])
        elif c[i][t] == 2:
            chick.append([i,t])

def way(x,y,x1,y1):
    return abs(x-x1) + abs(y-y1)

ans = float("inf")
for t in combinations(chick,m):
    ww = 0
    for p in house:
        chic_way = []
        for k in t:
            chic_way.append(way(k[0],k[1],p[0],p[1]))
        ww += min(chic_way)
    if ww < ans:
        ans = ww
print(ans)

---