[백준] 치킨 배달

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

15686번: 치킨 배달

조합을 이용한 구현 문제입니다.

 

우선 문제부터 간단하게 요약하면, 

도시에 치킨 집들과, 일반 가정집들이 있습니다. 이 때, 가정집에서 가장 가까운 치킨 집 까지의 택시거리를 치킨 거리라고 정의합니다.

ps. 거리의 종류에 대한 포스팅도 흥미로운 주제가 될 것 같습니다... 언젠가 기회가 되면 포스팅해보는 것으로...

도시에서 치킨집들을 M개 만큼만 골라서 가정집들의 치킨거리의 합이 최소가 되도록 하고싶은 상황입니다. 이러한 상황에 부합할 때의 치킨거리의 합을 return해야 합니다.

 

좀더 자세한 내용은 직접 링크를 통해 문제를 읽어보는 것이 정확할 것 같습니다.

 

<Solution>

얼핏 보기에는 bfs등이 생각날 수 있지만, 문제 상황자체가 bfs를 돌리기에는 녹녹치 않아 보입니다. 

 

어떤 방법을 사용해야 할지 생각을 해봅시다.

 

"치킨거리"를 구할 때는 단순하게 치킨집과 집의 좌표 차이의 절댓값을 계산하면 단 한번의 계산으로 거리를 구할수 있다는 점을 이용합시다. 

더불어서, 집의 갯수는 2N개 이하이고, 치킨집의 갯수는 많아봤자 13개인 문제조건을 이용합시다. (노가다를 해도 생각보다 크지 않을 것 같다는 생각이 듭니다)

 

이 두조건을 이용해 만약 노가다의 형태(brute force형태)로 접근을 했을 때, 어느정도의 복잡도가 나올지를 예상해 봅시다. 

 

brute force 시나리오는 다음과 같습니다.

1. 13개의 치킨 집에서 M개를 뽑습니다 (조합을 이용) 2. 이 M개와 2N개의 집들의 택시거리를 통해 각각의 집들에 대한 택시거리를 구합니다. 3. 이렇게 구한 결과를 비교하여 최종 답안을 도출합니다.

만약 이 시나리오가 최악으로 진행되는 상황을 생각해 봅시다. 

 

1번과정 -> 13개의 치킨집에서 M개를 뽑는 것은 13C7 or 13C6으로 1716이 최댓값입니다. (숫자가 커지는 상황을 예시로 들었습니다. 13C13 = 1 등의 경우 값이 굉장히 작음)

2번과정 -> N의 최댓값은 50이므로 2N = 100인 상황에서 7개의 치킨집과 택시거리 연산을 하게 되면, 100*7 = 700 회의 연산을 하게 됩니다.

 

1, 2 과정은 같은 for loop로 진행 될 것이므로 곱해봅니다. 1716*700 = 1,201,200

 

생각보다 최악을 가정해도 크지 않은 숫자가 나오는 것을 알 수 있고, 이렇게 구현을 하면 문제를 해결할 수 있습니다. (물론 정확한 연산 횟수는 이후의 비교과정 또한 포함 해야 하지만, 대략적인 10의 몇제곱의 복잡도인지 정도만 확인용으로 계산하였습니다.)

 

실제 구현은 아래와 같습니다.

import sys
import itertools

N, M = list(map(int, sys.stdin.readline().rstrip().split()))

graph = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]

house = []
chicken = []

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            house.append((i,j))
        elif graph[i][j] == 2:
            chicken.append((i,j))
        
nCr = itertools.combinations(chicken, M)

ans = int(2e9)
for e_ in nCr:
    sum_ = 0
    # find min distance to chicken
    for h in house:
        min_ = int(2e9)
        for e in e_:
            tmp = (abs(h[0]-e[0]) + abs(h[1]-e[1]))
            min_ = tmp if (min_ > tmp) else min_

        sum_ += min_
    ans = sum_ if (ans>sum_) else ans

print(ans)