[Gold V] 치킨 배달 - 15686

문제 링크

성능 요약

메모리: 34952 KB, 시간: 468 ms

분류

구현, 브루트포스 알고리즘, 백트래킹

문제 설명

크기가 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개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

---

문제 풀이

문제 분석

이 문제는 N x N 크기의 도시에서 최대 M개의 치킨집을 남겼을 때, "도시의 치킨 거리"가 최소가 되는 값을 찾는 것이 목표입니다. 도시의 치킨 거리는 모든 집 각각의 "치킨 거리"를 합한 값입니다. 여기서 집의 치킨 거리는 해당 집에서 가장 가까운 치킨집까지의 거리이며, 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 맨해튼 거리인 |r1-r2| + |c1-c2|로 계산됩니다.

입력은 N과 M, 그리고 N줄에 걸쳐 도시의 정보(0: 빈 칸, 1: 집, 2: 치킨집)가 주어집니다. N은 최대 50, M은 최대 13입니다. 특히, 전체 치킨집의 개수가 13개 이하라는 중요한 제약 조건이 있습니다. 출력은 최소 도시 치킨 거리입니다.

접근 방법

문제의 핵심은 "전체 치킨집 중 M개를 선택하는" 것입니다. M의 최대값이 13이고, 전체 치킨집의 개수 또한 최대 13개라는 제약 조건 덕분에, 이 문제는 브루트포스(완전 탐색) 방식으로 해결할 수 있습니다. 즉, 전체 치킨집 중에서 M개를 선택하는 모든 가능한 경우의 수를 탐색하고, 각 경우마다 도시의 치킨 거리를 계산하여 최소값을 찾으면 됩니다.

파이썬의 itertools.combinations를 사용하면 전체 치킨집 중 M개를 뽑는 모든 조합을 효율적으로 생성할 수 있습니다. 각 조합에 대해 모든 집을 순회하며, 해당 집에서 선택된 M개의 치킨집 중 가장 가까운 치킨집까지의 거리를 계산하고, 이 값들을 모두 더해 도시 치킨 거리를 구합니다. 이 과정을 모든 조합에 대해 반복하여 얻은 도시 치킨 거리들 중 최솟값을 최종 결과로 출력합니다.

구현 설명

1. 입력 처리 및 초기 데이터 준비

• n과 m을 입력받습니다.
• 도시의 정보를 graph 리스트에 저장합니다.
• 도시를 순회하면서 집의 위치는 house 리스트에 [r, c] 형태로 저장하고, 치킨집의 위치는 chicken 리스트에 [r, c] 형태로 저장합니다. 이렇게 하면 나중에 집과 치킨집을 쉽게 참조할 수 있습니다.

2. M개의 치킨집 조합 선택

• itertools.combinations(chicken, m) 함수를 사용하여 chicken 리스트(전체 치킨집들의 좌표 리스트)에서 m개의 치킨집을 선택하는 모든 가능한 조합을 생성합니다. 이 조합들은 arr 변수에 저장됩니다. arr는 이터레이터이므로 메모리 효율적입니다.

3. 각 조합별 도시 치킨 거리 계산

• arr에 있는 각각의 치킨집 조합 (i)에 대해 다음 과정을 반복합니다.
  • 현재 조합의 "도시 치킨 거리" 합을 저장할 sum1 변수를 0으로 초기화합니다.
  • house 리스트에 있는 모든 집 (x, y)에 대해 다음 과정을 반복합니다.
    • 현재 집 (x, y)에서 가장 가까운 치킨집까지의 거리를 저장할 mi 변수를 무한대(float("inf"))로 초기화합니다.
    • 현재 선택된 m개의 치킨집 조합 i에 있는 모든 치킨집 (dx, dy)에 대해 다음을 수행합니다.
      • 맨해튼 거리 abs(x - dx) + abs(y - dy)를 계산합니다.
      • 이 거리가 mi보다 작으면 mi를 해당 거리로 업데이트합니다.
    • 현재 집의 치킨 거리(mi)가 구해지면, 이 값을 sum1에 더합니다.
  • 모든 집에 대한 치킨 거리 합산이 끝나면, sum1은 현재 치킨집 조합(i)에 대한 도시 치킨 거리가 됩니다. 이 값을 result 리스트에 추가합니다.

4. 최소 도시 치킨 거리 출력

• 모든 치킨집 조합에 대한 도시 치킨 거리들이 result 리스트에 저장되면, 이 result 리스트에서 최솟값을 찾아 출력합니다. 이것이 문제에서 요구하는 최소 도시 치킨 거리입니다.

⏱복잡도 분석

시간 복잡도

• 초기 데이터 준비: N x N 도시를 순회하며 집과 치킨집의 위치를 찾는 데 O(N^2)의 시간이 걸립니다. (N은 최대 50)
• 조합 생성 및 순회:
  • 전체 치킨집의 개수를 C_total이라고 할 때 (최대 13개), C_total개의 치킨집 중 M개를 선택하는 조합의 수는 C(C_total, M)입니다. (최대 C(13, 6) 또는 C(13, 7) = 1716가지)
  • 각 조합에 대해:
    • 모든 집(H_total개, 최대 2N개, 즉 100개)을 순회합니다. O(H_total)
    • 각 집에서 선택된 M개의 치킨집까지의 거리를 각각 계산하고 최솟값을 찾습니다. O(M)
  • 따라서, 각 조합에 대한 도시 치킨 거리 계산은 O(H_total * M) 시간이 걸립니다.
• 총 시간 복잡도: O(N^2 + C(C_total, M) * H_total * M)
  • N^2은 50^2 = 2500
  • C(13, 6) * (2*50) * 13 = 1716 * 100 * 13 = 2,230,800
  • 최악의 경우 약 2.2백만 번의 연산으로, 1초 내에 충분히 해결 가능합니다.

공간 복잡도

• graph 리스트: O(N^2) (N은 최대 50)
• house 리스트: 최대 2N개 (최대 100개), 각 요소는 2개의 정수. O(N)
• chicken 리스트: 최대 13개, 각 요소는 2개의 정수. O(1) (상수)
• arr (combinations 이터레이터): 실제 조합을 한 번에 모두 메모리에 저장하지 않고 필요할 때마다 생성하므로, 추가적인 공간 복잡도는 매우 작습니다.
• result 리스트: 최대 C(C_total, M)개의 정수를 저장합니다. (최대 1716개). O(C(C_total, M))
• 총 공간 복잡도: O(N^2 + C(C_total, M))
  • N^2이 C(C_total, M)보다 훨씬 크므로, 실질적인 공간 복잡도는 O(N^2)입니다.
  • 50x50 배열에 대한 정보는 2500칸으로, 충분히 메모리에 저장 가능합니다.

핵심 포인트

1. 조합(Combination) 활용: 전체 치킨집의 개수가 최대 13개로 매우 작다는 점을 이용하여, itertools.combinations를 통해 M개의 치킨집을 선택하는 모든 가능한 경우의 수를 효율적으로 생성하는 것이 이 문제의 핵심입니다.
2. 맨해튼 거리 계산: 두 칸 (r1, c1)과 (r2, c2) 사이의 거리를 문제에서 제시된 |r1-r2| + |c1-c2| 맨해튼 거리 공식에 따라 정확하게 계산하는 것이 중요합니다.
3. 도시 치킨 거리의 정의: 각 "집"이 "선택된 치킨집들 중 가장 가까운 치킨집"과의 거리를 갖는다는 점, 그리고 이 모든 집의 치킨 거리를 합산한 값이 "도시 치킨 거리"가 된다는 정의를 정확히 이해하고 구현해야 합니다. 각 조합마다 모든 집을 순회하며 이 계산을 반복하는 것이 중요합니다.

풀이 코드

import sys
from collections import deque
from itertools import combinations

n,m = map(int,sys.stdin.readline().split())

graph = []
for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))


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])

arr = combinations(chicken,m)

result = []

for i in arr:
    sum1 = 0
    for x,y in house:
        mi = float("inf")
        for dx,dy in i:
            temp = abs(x-dx)+abs(y-dy)
            if temp  mi:
                mi = temp
        sum1+=mi

    result.append(sum1)

print(min(result))