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

728x90

백준 15686번 치킨 배달 (백트래킹)

1. 문제

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

2. 풀이

목표: M개의 치킨집을 선택하여, 그 치킨집들과 집들 간의 치킨 거리 합이 되소가 되도록 하는 것

1) 치킨집과 집 정보 저장

치킨집과 집을 배열에 (r, c) 형태로 저장한다.

chicken = []    # 치킨집 저장할 배열: (r, c)
house = []
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            house.append((i, j))
        elif city[i][j] == 2:
            chicken.append((i, j))

2) 백트래킹(Backtracking)

selected: 현재 선택된 치킨집 인덱스 배열
start: 탐색을 다시 시작할 인덱스

start 인덱스는 중복된 선택을 방지하고, 치킨집을 순차적으로 선택하게 하여 불필요한 재탐색을 줄이는 데 중요한 역할을 한다.

특히 for문 안에서 start부터 탐색하고, backtrack(selected, i+1)으로 호출하여 이미 선택된 치킨집을 다시 선택하지 않도록 하여 효율성을 높인다.

def backtrack(selected, start):
    global min_result
    if len(selected) == m:
        min_result = min(min_result, dist(house, selected))
        return
    for i in range(start, len(chicken)):
        if i not in selected:
            selected.append(i)
            backtrack(selected, i+1)
            selected.pop()

3) 치킨 거리 계산

각 집에서 가장 가까운 치킨집까지의 거리를 계산하는 함수이다.

def dist(house, chicken_idx):
    city_dist = 0
    for r1, c1 in house:
        chick_dist = 2*n
        for i in chicken_idx:
            r2, c2 = chicken[i]
            chick_dist = min(chick_dist, abs(r1-r2)+abs(c1-c2))
        city_dist += chick_dist
    return city_dist

3. 코드

# 15686번. 치킨 배달

import sys
input = sys.stdin.readline

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

city = [list(map(int, input().split())) for _ in range(n)]

min_result = float('inf')

def dist(house, chicken_idx):
    city_dist = 0
    for r1, c1 in house:
        chick_dist = 2*n
        for i in chicken_idx:
            r2, c2 = chicken[i]
            chick_dist = min(chick_dist, abs(r1-r2)+abs(c1-c2))
        city_dist += chick_dist
    return city_dist

def backtrack(selected, start): # selected: 선택된 치킨집 인덱스 배열 
    global min_result
    
    # 치킨집 M개 선택 시 도시의 치킨 거리 계산
    if len(selected) == m:
        # 치킨 거리 계산
        min_result = min(min_result, dist(house, selected))
        return
    
    for i in range(start, len(chicken)):
        if i not in selected:
            selected.append(i)
            backtrack(selected, i+1)
            selected.pop()

chicken = []    # 치킨집 저장할 배열: (r, c)
house = []
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            house.append((i, j))
        elif city[i][j] == 2:
            chicken.append((i, j))

backtrack([], 0)
print(min_result)

4. 결과