[알고리즘] 치킨 배달 (Brute force-GoldⅤ)

📘 알고리즘 노트

문제를 해결하기 위해 구현해야되는 로직 정리

 

필요한 로직

• ✨ m개의 치킨집을 무작위로 선택할 combination 로직
• ✨ 선택된 치킨집과 집의 최소 치킨거리계산
• ✨ 치킨거리를 누적하면서 조합이 바뀔때마다 최소 누적치킨거리로 갱신 

 

문제 설명

최대 M개의 치킨집을 골라 치킨거리의 합의 최솟값을 구하는 문제

 

조건

집과 치킨집의 좌표를 (r1,c1) (r2,c2)라고 했을 때 두 점사이의 거리는

| r1 - r2 | + | c1 - c2 |로 계산

 

제한사항

• N : (2<=N<=50), M : (1<=M<=13)
• 도시의 정보는 0,1,2 => 0은 빈칸, 1은 집, 2는 치킨집
• 집의 개수<=2N, 적어도 1개 존재, M<=치킨집의개수<=13 

 

combination을 통해 m개를 뽑아서 리스트에 담기

# itertools 라이브러리 사용
from itertools import combinations

# 모든 조합을 구하기 위해 치킨집의 위치를 튜플로 삽입
for i in range(n):
    for j in range(n):
        if matrix[i][j] == 2:
           chicken.append((i,j))
           
comb = []
# m개를 뽑아서 치킨집에 리스트에 넣기
for i in combinations(chicken,m):
    comb.append(i)

 

m개 치킨집으로 구성된 모든 조합에 대한 치킨거리의 최소 누적합 구하기

result = 999999
for c in range(len(comb)): # 경우의 수 각각에 대해 거리 계산
    distance = 0     # 조합에 대한 누적합 갱신(최소값)
    for i in range(n):
        for j in range(n):
            if matrix[i][j] == 1:
                min_dist = 999999
                for k in range(m): # 현재 집에 대해서 치킨집 조합에 따른 거리 계산
                    x_dis = abs(i-comb[c][k][0])
                    y_dis = abs(j-comb[c][k][1])
                    min_dist = min(min_dist,x_dis+y_dis) # 치킨거리를 설정(최솟값)
                distance += min_dist # 치킨 거리 누적
    result = min(result,distance)

 

전체 코드

# 문제 이해
# 행렬은 1,1 부터 시작
# 치킨거리 = 집과 가장 가까운 치킨집 사이 거리
# 도시의 치킨 거리는 모든 집의 치킨 거리 합
# 0은 빈칸 1은 집 2는 치킨
# 도시에서 가장 수익을 많이 낼 수 있는 치킨집은 M개
# 나머지 치킨집 폐업시키기
# 도시의 치킨 거리의 합이 가장 작게 만들기

# 접근
# combination을 통해 모든 m개의 치킨집의 경우의 수를 구한다.
# 선택된 치킨집과 집 사이의 거리를 최소거리인 걸로 선택하며 갱신해준다.
# 조합이 바뀌고 모든 경우의 수를 구했을때 최솟값이면 갱신해준다.

from itertools import combinations

n,m = map(int,input().split())

matrix = []
chicken = []
# 지도 구현
for i in range(n):
    matrix.append(list(map(int,input().split())))

# 모든 조합을 구하기 위해 치킨집의 위치를 튜플로 삽입
for i in range(n):
    for j in range(n):
        if matrix[i][j] == 2:
           chicken.append((i,j))   
comb = []
# m개를 뽑아서 치킨집에 리스트에 넣기
for i in combinations(chicken,m):
    comb.append(i)
    
result = 999999
for c in range(len(comb)):
    distance = 0
    for i in range(n):
        for j in range(n):
            if matrix[i][j] == 1:
                min_dist = 999999
                for k in range(m):
                    x_dis = abs(i-comb[c][k][0])
                    y_dis = abs(j-comb[c][k][1])
                    min_dist = min(min_dist,x_dis+y_dis)
                distance += min_dist
    result = min(result,distance)
print(result)