[Baekjoon] 백준 15686번 - 치킨 배달 by Python (백트래킹)

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

 

아이디어

• 치킨집의 개수 C개의 경우 C개의 치킨집 중 M개를 선택하는 모든 조합 : 1716개 조합
• 각 조합에 대해 모든 집의 치킨 거리 계산(집의 개수 H, 치킨집 개수 M) : 최악의 경우 1300
• 최악의 경우 O(1716⋅1300)≈2,230,800 

 

즉 2.23×10^6 의 연산이 필요하기 때문에 브루투포스와 백트래킹을 활용해 모든 치킨집의 조합을 확인하며 계산하여 정답을 도출할 수 있다.

 

 

코드

입력부

N, M = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(N)]
result = int(1e9)
store = []
house = []
for i in range(N):
    for j in range(N):
        if city[i][j] == 2:
            store.append((i, j))
        elif city[i][j] == 1:
            house.append((i, j))

 

주어진 입력을 모두 저장하고, 배열을 탐삭하며 배열 속 집의 위치와, 치킨집의 위치를 저장해주었다.

 

백트래킹 부분

def back(start):
    global result 
    if M == len(chose):
        result = min(result, calculate_distance())
        return
    for i in range(start, len(store)):
        chose.append(store[i])
        back(i+1)
        chose.pop()

 

계속 새로운 치킨집을 선택하며 정해진 M 만큼의 치킨집이 선택되었을 때 도시의 치킨 거리를 계산한다.

이후에는 치킨집 선택을 해제하며 다음 치킨집 조합 탐색으로 이어나간다.

 

치킨 거리 계산 부분

def calculate_distance():
    city_distance = 0
    for h in house:
        temp_distance = int(1e9)
        for s in chose:
            distance = abs(s[0]-h[0]) + abs(s[1]-h[1])
            temp_distance = min(temp_distance, distance)
        city_distance += temp_distance
    return city_distance

 

각 집에 대해 현재 선택된 M개의 치킨집과의 최단 거리를 계산한다. 이때 abs를 활용해 절대값을 구해주었다.

이후 도시의 치킨 거리를 만들어 최종 반환한다.

 

전체코드

def calculate_distance():
    city_distance = 0
    for h in house:
        temp_distance = int(1e9)
        for s in chose:
            distance = abs(s[0]-h[0]) + abs(s[1]-h[1])
            temp_distance = min(temp_distance, distance)
        city_distance += temp_distance
    return city_distance


def back(start):
    global result 
    if M == len(chose):
        result = min(result, calculate_distance())
        return
    for i in range(start, len(store)):
        chose.append(store[i])
        back(i+1)
        chose.pop()
        
        
N, M = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(N)]
result = int(1e9)
store = []
house = []
for i in range(N):
    for j in range(N):
        if city[i][j] == 2:
            store.append((i, j))
        elif city[i][j] == 1:
            house.append((i, j))

chose = []
back(0)

print(result)

 

전반적으로 간단한 백트래킹 문제였다. 큰 조건이 없기 때문에 쉽게 풀 수 있었다.