🍗 치킨 배달

solved_ac[Class4][치킨 배달](https://www.acmicpc.net/problem/15686)

문제

---

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2,
(5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다.
따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

---

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

예제 입력 1

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

예제 출력 1

5

예제 입력 2

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

예제 출력 2

10

예제 입력 3

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

예제 출력 3

11

예제 입력 4

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

예제 출력 4

32

📖 알고리즘

TRY 1 (플로이드 와샬)

이 문제를 그래프 탐색 문제라고 오인하여 접근했다.

Value가 1인 모든 노드에서 2인 모든 노드로 가는 최소비용을 구한 후 그 최소비용들 중에서의 최소를 한 번 더 걸러주면 된다고 생각했다.

치킨집 M개를 선택한다는 조건은 For문을 통하여 단순 구현하면 된다고 생각했지만 이는 내가 플로이드 와샬 알고리즘을 잘 못 알고 있어서 발생한 착각이다.

[플로이드 와샬 알고리즘은 Weight가 있는 그래프에서 모든 노드에서 모든 노드로 가는 최소 비용을 구할 때 사용한다.]

그런데 이 문제에서는 Weight가 없다. 따라서 플로이드 와샬 알고리즘을 사용하는 것은 적절치 않다.

TRY 2 (백트래킹)

결국 "알고리즘 분류" 힌트를 참고하였는데 문제가 백트래킹으로 분류되어 있었다.

[백트래킹은 모든 경우의 수를 확인해야할 때 & 반복문으로 확인 불가한 경우 사용한다.]

이를 본 문제에 적용시켜보면 치킨집 M개를 선택하는 모든 경우의 수를 확인해야 하고 그 M개가 미지수이므로 For문을 사용하여 설계를 하지 못 한다. 따라서 이 문제는 백트래킹으로 풀 수 있는 문제이다.

그런데 이 또한 백트래킹으로 구현하기가 까다로웠다. 그래서 결국 솔루션을 참고하려고 하였으나 대부분의 사람들이 백트래킹을 사용하여 풀지 않고 완전탐색 접근법으로 문제를 풀었다.

왜 브루트 포스를 사용할까?

TRY 3 (브루트 포스)

[브루트 포스는 모든 경우의 수를 확인해야할 때 사용한다.]

백트래킹과 차이점은 "반복문으로 확인 불가한 경우"라는 조건이 빠졌다. 이 문제를 다시 고찰해 보았을 때, 이 문제는 반복문으로 확인이 가능하다.

바로 "조합"을 이용하면 M개의 미지수만큼 반복문을 돌려줄 수 있다.

따라서 백트래킹보다는 조합을 이용한 완전탐색 기법으로 푸는 것이 조금 더 맞는 풀이가 아닐까 생각해본다.

📐 설계

• 치킨 M개를 선택한다.(조합)
  • 모든 집과
    • 모든 선택한 치킨을 순회하며
      • 최소 거리를 구한다. = 치킨 거리
    • 도시 치킨 거리를 "치킨 거리"만큼 증가시킨다.
  • 최소 도시 치킨 거리를 갱신시킨다.

👨🏻‍💻 CODE

import sys
input = sys.stdin.readline
from itertools import combinations
INF = int(1e9)
N, M = map(int,input().split())

house = []
chicken = []

for i in range(N):
    temp = list(map(int,input().split()))

    for j in range(N):
        if temp[j] == 1:
            house.append((i,j))
        if temp[j] == 2:
            chicken.append((i,j))

answer = INF
for c in combinations(chicken,M):
    city_distance = 0
    for h in house:
        chicken_distance = INF
        for i in range(M):
            chicken_distance = min(chicken_distance,abs(c[i][0]-h[0])+abs(c[i][1]-h[1]))
        city_distance += chicken_distance
    answer = min(answer,city_distance)

print(answer)