BOJ - 치킨 배달 15686번 (python)

❓ 문제 - 백준 치킨 배달 15686번 - python 풀이법

출처 

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

15686번: 치킨 배달

 

 

📝 문제해결법

1. 이 문제는 BFS(조합)+구현으로 풀었다.

• combination() 함수를 사용하여 기존에 있는 치킨 집에서 m개의 치킨집을 선택하여 해당 치킨집만을 운영했을 때 도시의 치킨 거리를 구하여 도시의 치킨 거리의 최솟값을 갱신해준다.
• find_dist() 함수를 사용하여 현재 집 위치에서 선택된 치킨 집까지의 치킨 거리를 구하고 최소가 되는 치킨 거리를 찾아 도시의 치킨 거리로 합해준다. 또한 구한 도시의 치킨 거리와 min_value 변수를 비교하여 도시의 치킨 거리의 최솟값을 계속 갱신해준다.

 

 

💻 소스코드

n, m = map(int, input().split())
graph = []
chicken = []
home = []
for i in range(n):
    data = list(map(int, input().split()))
    for j in range(n):
        if data[j] == 2:
            chicken.append([i, j])
        elif data[j] == 1:
            home.append([i, j])

def combination(lst, num):
    result = []
    if num > len(lst):
        return result
    if num == 1:
        for i in lst:
            result.append([i])
    elif num > 1:
        for i in range(len(lst)-num+1):
            for temp in combination(lst[i+1:], num-1):
                result.append([lst[i]]+temp)
    return result

min_value = int(1e9)


def find_dis(c):
    global  min_value
    all_c = 0
    for h_x, h_y in home:
        min_c = 2*n+1
        for c_x, c_y in c:
            dist = (abs(h_x-c_x) + abs(h_y-c_y))
            min_c= min(min_c, dist)
        all_c += min_c
    min_value = min(min_value, all_c)


for c in combination(chicken, m):
    find_dis(c)

print(min_value)