[Implementation] 이코테 “치킨 배달” Python 풀이

문제

• 크기가 N x N인 도시가 있습니다.

• 도시는 1 x 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개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력합니다.

입력 예시

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

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

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

출력 예시

5

10

11

풀이

• 전체 치킨집에서 M개의 치킨집을 고른다(조합).
• 각 조합(M개의 치킨집)에 따른, 각 집에서의 치킨 거리의 합(도시의 치킨 거리)을 계산한다.
• 조합 별 도시의 치킨 거리 결과에서, 도시의 치킨 거리 합이 가장 작은 값을 출력한다.

예제 코드

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

import sys
from itertools import combinations

# 도시의 크기와 치킨집의 최대 개수 입력
n, m = map(int, sys.stdin.readline().split())

# 집 위치
house = []
# 치킨집 위치
chicken = []

# 집과 치킨집의 위치를 저장
for i in range(n):
    row = list(map(int, sys.stdin.readline().split()))
    for j in range(n):
        # 집이라면
        if (row[j] == 1):
            house.append((i, j))
        # 치킨집이라면
        elif (row[j] == 2):
            chicken.append((i, j))

# 전체 치킨집에서 M개를 뽑는 조합 계산
total_chick_combi = list(combinations(chicken, m))

# 치킨집 조합에 따른 도시의 치킨 거리 결과에서, 최소값을 계산하기 위한 변수
result = int(1e9)

# 치킨집 조합에 따른 도시의 치킨 거리 계산
for chick_combi in total_chick_combi:

    # 도시의 치킨 거리를 계산하기 위한 변수
    sum_chick_dist = 0

    # 각 집에서의 치킨 거리를 계산
    for house_location in house:

        # 최소의 치킨 거리를 계산하기 위한 변수
        chick_dist = int(1e9)

        for x, y in chick_combi:
            # 각 집에서, 치킨집 별 치킨 거리 비교
            chick_dist = min(chick_dist, abs(house_location[0]-x) + abs(house_location[1]-y))

        # 해당 집의 치킨 거리를 도시의 치킨 거리 결과에 덧셈 
        sum_chick_dist += chick_dist

    # 치킨집 조합에 따른 도시의 치킨 거리 결과에서, 최소값을 계산
    result = min(result, sum_chick_dist)

print(result)

참고

• 이것이 취업을 위한 코딩 테스트다. with python