[백준] 치킨 배달 15686번 (python) 조합

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

 

풀이 방법

M개의 치킨 집을 선택하는 과정에서 순서에 상관없는 조합을 이용해야 한다.

조합을 구하기 위해 백트레킹 dfs를 사용했다.

아래의 코드에서 chosen 배열에 넣은 후 dfs를 수행하고 chosen배열에서 pop을 통해 백 트레킹을 수행했다.

 

치킨 거리 계산은 그냥 유클리드 계산으로 수행하면 된다.

 

N, M = map(int, input().split()) ## N, M 입력받기
city = []
for i in range(N): ## city 입력 받기
    city.append(input().split())
house = []
store = []
chosen = []
ans = 987654321
for i in range(N): ## 치킨 집과 집을 저장한다.
    for j in range(N):
        if city[i][j] == '1': 
            house.append([i, j])
        elif city[i][j] == '2':
            store.append([i, j])

def distance(a, b, x, y): ## 유클리드 거리를 계산한다.
    return abs(a - x) + abs(b - y)

def cal_dis(): ## 현재의 최소 치킨 거리를 계산한다.
    ret = 0
    for i, j in house: ## 모든 집을 돌며
        min_dis = 987654321 ## 현재 집에서의 최소 치킨집 까지의 거리
        for k in chosen: ## 선택된 치킨 집
            min_dis = min(min_dis, distance(i, j, store[k][0], store[k][1]))
        ret += min_dis ## 현재집에서 가장 작은 치킨 집 거리 계산
    return ret

def dfs(idx, cnt): ## 현재 치킨 집 idx, 치킨 집 수, 지금 까지의 거리
    global ans
    if cnt == M: ## 만약 M개의 치킨 집이 선택이 되었으면 치킨 거리 계산하는 로직 수행
        ans = min(ans, cal_dis())
        return 
    for i in range(idx + 1, len(store)): ## 
        chosen.append(i) ## i 번째 더하기
        dfs(i, cnt + 1)
        chosen.pop() ## i 번째 빼기
    return
for i in range(len(store)): ##  N-1 까지 잖아
        chosen.append(i) ## i 번째 더하기
        dfs(i, 1)
        chosen.pop() ## i 번째 빼기
print(ans)