[15686] 치킨 배달

집과 치킨집 좌표 추출

지도를 매번 처음부터 끝까지 훑는 건 시간이 너무 오래 걸린다. 그래서 가장 먼저 지도에서 집이 있는 위치와 치킨집이 있는 위치만 따로 뽑아 주소록을 만든다.

# 입력 받기

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

houses = []

chickens = []

# graph 입력 받기

for r in range(n):

    row = list(map(int, input().strip().split()))

    for c in range(n):

        if row[c] == 1:

            houses.append((r, c))

        elif row[c] == 2:

            chickens.append((r, c))

치킨집 조합 생성

전체 치킨집 중에서 남길 개수만큼 고르는 모든 경우의 수를 짠다. 이때 백트래킹을 사용한다. 치킨집 하나를 선택해 장바구니에 담고 다음 후보를 살핀 뒤, 계산이 끝나면 다시 그 치킨집을 빼고 다른 후보를 담는 과정을 반복하며 모든 조합을 만든다.

def dfs(idx, count):

    global min_city_distance

    # 종료 조건

    if count == m:

        city_distance = calcuate(select_chickens)

        min_city_distance = min(min_city_distance, city_distance)

        return

    # 후보 탐색

    for i in range(idx, len(chickens)):

        select_chickens.append(chickens[i])

        dfs(i + 1, count + 1)

        select_chickens.pop()

 

각 집의 최단 거리 계산

치킨집 조합이 하나 완성될 때마다 거리 측정을 시작한다. 모든 집을 하나씩 순회하며, 방금 선택된 치킨집들 중 해당 집과 가장 가까운 곳까지의 거리를 구한다. 이것이 각 집의 치킨 거리가 된다.

def calcuate(selected):

    total_distance = 0

    for hr, hc in houses:

        temp_min = float("inf")

        for cr, cc in selected:

            dist = abs(hr - cr) + abs(hc - cc)

            temp_min = min(temp_min, dist)

        total_distance += temp_min

    return total_distance

 

도시 전체 거리 합산 및 비교

모든 집의 치킨 거리를 다 더해서 해당 조합의 최종 점수를 낸다. 새로운 조합이 만들어질 때마다 이 과정을 반복하며, 지금까지 나온 점수 중 가장 낮은 값을 계속 업데이트한다.

 

최적의 결과 도출

모든 경우의 수를 전부 따져본 후, 마지막까지 살아남은 가장 작은 합계 점수를 정답으로 출력한다.

 

치킨 배달 최악의 연산량 계산

1. 치킨집 조합 만들기

• 상황: 치킨집 13개 중 6개를 고를 때 (가장 가짓수가 많은 경우)
• 가짓수: 1,716가지

2. 한 번의 조합당 거리 계산

• 상황: 집 100개와 선택된 치킨집 6개를 일일이 비교할 때
• 계산량: 100개(집) × 6개(치킨집) = 600번

3. 전체 연산 횟수

• 합계: 1,716가지(조합) × 600번(계산) = 1,029,600번

 

 

import sys

input = sys.stdin.readline

# 입력 받기

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

houses = []

chickens = []

# graph 입력 받기

for r in range(n):

    row = list(map(int, input().strip().split()))

    for c in range(n):

        if row[c] == 1:

            houses.append((r, c))

        elif row[c] == 2:

            chickens.append((r, c))

select_chickens = []

min_city_distance = float("inf")

def calcuate(selected):

    total_distance = 0

    for hr, hc in houses:

        temp_min = float("inf")

        for cr, cc in selected:

            dist = abs(hr - cr) + abs(hc - cc)

            temp_min = min(temp_min, dist)

        total_distance += temp_min

    return total_distance

def dfs(idx, count):

    global min_city_distance

    # 종료 조건

    if count == m:

        city_distance = calcuate(select_chickens)

        min_city_distance = min(min_city_distance, city_distance)

        return

    # 후보 탐색

    for i in range(idx, len(chickens)):

        select_chickens.append(chickens[i])

        dfs(i + 1, count + 1)

        select_chickens.pop()

dfs(0, 0)

print(min_city_distance)