백준 15686번 : 치킨 배달 - 파이썬 (python)

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

15686번: 치킨 배달

 

* 파이썬 조합 (combinations)

from itertools import combinations를 import한 후 combinations(반복 가능한 객체, 뽑을 개수)로 사용

from itertools import combinations
data = [[0, 1], [0, 3], [1, 1]]
comb = list(combinations(data, 2))
print(comb)

#result
#[([0, 1], [0, 3]), ([0, 1], [1, 1]), ([0, 3], [1, 1])]

조합 라이브러리를 이용하여 가능한 치킨 집의 조합을 생성하여 해결한다 !

 

* 아이디어

(1) 입력받은 도시 정보를 검사

     → 1이면 house에 인덱스 번호 [i, j]를 추가하고 2이면 chicken에 인덱스 번호 [i, j]를 추가한다.

(2) 조합 라이브러리를 이용해 가능한 치킨 집의 조합을 찾는다.

(3) 집의 위치와 각 치킨의 거리를 구하고 가장 작은 값을 distance에 추가한다.

(4) 현재 distance 배열에는 각 집의 최소값이 나열되어 있으므로

    각 조합별 도시의 치킨 거리(모든 집의 치킨 거리의 합)를 구하기 위해 집의 개수만큼씩 나누어 합을 구한다.

(5) 각각의 합을 result에 추가하고 result의 최소값을 구한다.

    → 즉, 도시 치킨 거리의 최소값

 

from itertools import combinations

# 도시의 크기 N
# 폐업시키지 않을 치킨집 최대 개수 M
n, m = map(int, input().split())

# 도시 정보
city = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    city[i] = list(map(int, input().split()))

chicken = []
house = []
for i in range(n):
    for j in range(n):
        # 집 위치
        if city[i][j] == 1:
            house.append([i, j])
        # 치킨 집 위치
        if city[i][j] == 2:
            chicken.append([i, j])

# 치킨 집 조합
comb = list(combinations(chicken, m))

distance = []
result = []
for i in range(len(comb)):
    for h in house:
        d = []
        for j in range(m):
            d.append(abs(h[0] - comb[i][j][0]) + abs(h[1] - comb[i][j][1]))
        distance.append(min(d))

distance_sum = 0
for i in range(len(distance)):
    distance_sum += distance[i]
    if (i+1) % len(house) == 0:
        result.append(distance_sum)
        distance_sum = 0

print(min(result))

 

 

 

https://github.com/501501/codingTest/blob/master/%EA%B5%AC%ED%98%84/A13.py

GitHub - 501501/codingTest: 이것이 취업을 위한 코딩테스트다 with 파이썬