15686-백준-치킨 배달

1. 문제 출처

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

15686번: 치킨 배달

2. 풀이

처음에는 다음과 같이 치킨집의 개수가 M개가 되는 모든 경우의 수를 재귀로 구하였다.   

 

하지만 시간 초과 되었다...

# 입력 받기

N,M = map(int, input().split())

city = [0 for _ in range(N)]

result = []

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

# 치킨집 리스트와 주택 리스트를 생성한다.
chicken_list = []
home_list = []
for i in range(N):
    for j in range(N):
        if city[i][j] == 1:
            home_list.append([i,j])
        elif city[i][j] == 2:
            chicken_list.append([i,j])


    
    
# 재귀 함수를 이용하여 모든 경우에 수의 최솟값을 리스트에 저장한다.
def solution(store_list):
    
    global result
    if len(store_list) == M:
        result.append(total_distance(store_list))
        return
        
    
    for idx in range(len(store_list)):
        # index = idx 인값 제거
        temp = store_list.pop(idx)
        # 배열이 하나 제거된 리스트를 인수로 재귀 
        solution(store_list)
        # 제거한 값 제자리에 다시 추가 
        store_list.insert(idx,temp)

# 도시 치킨 거리 구하기
def total_distance(store_list):
    total = 0
    for home in home_list:
        min_dis = 2*N
        # 각 집에서 치킨집까지의 거리가 가장 짧은 것을 total에 더함
        for store in store_list:
            min_dis = min(min_dis ,distance(store,home))
        total+=min_dis
    return total

# 맨하튼 거리(치킨집 거리 구하기)
def distance(x,y):
    return abs(x[0]-y[0])+abs(x[1]-y[1])


solution(chicken_list)
print(min(result))

그래서 다음과 같이 itertools 의 combinations 함수를 이용하여 chicken_list 에서 원한 만큼 값을 뽑아와 비교하였다.

from itertools import combinations

N,M = map(int, input().split())

city = [0 for _ in range(N)]


for idx in range(N):
    city[idx] = list(map(int, input().split()))
    
chicken_list = []
home_list = []
for i in range(N):
    for j in range(N):
        if city[i][j] == 1:
            home_list.append([i,j])
        elif city[i][j] == 2:
            chicken_list.append([i,j])

    
    
    
def solution():
    # M만큼의 조합 리스트
    store_list = list(combinations(chicken_list , M))
    # result 값 초기화
    result  = total_distance(store_list[0])
    # 조합 중 도시 치킨 거리가 가장 작은 값 result에 저장 
    for idx in range(1,len(store_list)):
        result = min(result,total_distance(store_list[idx]))
    print(result)
        

def total_distance(store_list):
    total = 0
    for home in home_list:
        min_dis = 2*N
        for store in store_list:
            min_dis = min(min_dis ,distance(store,home))
        total+=min_dis
    return total
        
def distance(x,y):
    return abs(x[0]-y[0])+abs(x[1]-y[1])


solution()

결과는 성공