백준 15686번: 치킨 배달 (Python)

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

15686번: 치킨 배달

접근

dfs 알고리즘을 이용하여 주어진 치킨집 중 M개를 선택하는 함수를 설계하고, 현재 집들과 선택된 치킨집을 입력받아 도시 전체의 치킨 거리를 리턴해주는 check 함수를 이용하여 문제를 해결할 수 있었다.

2022.09.22 다시 풀기

각 집에서 치킨집까지의 거리를 미리 구하고 이를 오름차순으로 정렬해두어 계산속도를 빠르게 할 수 있다. 오름차순 정렬 값을 앞에서부터 탐색하여 해당하는 치킨집이 나올 경우 멈추면 모든 치킨집을 탐색하는 일 없이 가장 가까운 치킨집의 거리를 알 수 있다.

코드

from itertools import combinations as cb

N, M = map(int, input().split(" "))
house = []
chicken = []
for i in range(N):
    line = list(map(int, input().split(" ")))
    for j in range(N):
        if line[j] == 1:
            house.append([i, j])
        elif line[j] == 2:
            chicken.append([i, j])


def getDist(r1, c1, r2, c2):
    return abs(r1 - r2) + abs(c1 - c2)


chickenDistance = [[] for _ in range(len(house))]
for i in range(len(house)):
    hr, hc = house[i]
    for j in range(len(chicken)):
        cr, cc = chicken[j]
        chickenDistance[i].append((getDist(hr, hc, cr, cc), j))
    chickenDistance[i].sort()


def getChickenDistance(arr):
    global ans
    tmp = 0
    for i in chickenDistance:
        for j in i:
            if j[1] in arr:
                tmp += j[0]
                break
        if tmp >= ans:
            return
    ans = min(ans, tmp)


num_arr = [i for i in range(len(chicken))]
ans = float("inf")
for l in cb(num_arr, M):
    getChickenDistance(l)
print(ans)

N, M = map(int, input().split())
house = []
chicken = []
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(N):
        if tmp[j] == 1:
            house.append((i, j))
        elif tmp[j] == 2:
            chicken.append((i, j))
min_val = [float("inf")]
chicken_selected = []


def check(house_list, chicken_list):
    # 현재 주어진 집 리스트와 치킨집 리스트를 비교하여 도시의 치킨거리를 리턴해주는 함수
    chicken_distance = 0
    for h_i, h_j in house_list:
        tmp = float("inf")
        for c_i, c_j in chicken_list:
            tmp = min(tmp, abs(h_i - c_i) + abs(h_j - c_j))
        chicken_distance += tmp
    return chicken_distance


def dfs(depth, index):
    if M == depth:
        # 치킨집을 M개 모두 선택했을 경우 도시의 치킨거리를 계산하여 최소값 갱신
        min_val[0] = min(min_val[0], check(house, chicken_selected))
        return
    for i in range(index + 1, len(chicken)):
        # 치킨집을 순차적으로 선택하여 선택된 치킨집으로 선정하고 dfs 를 이용하여 개수 증가
        chicken_selected.append(chicken[i])
        dfs(depth + 1, i)
        chicken_selected.remove(chicken[i])


dfs(0, -1)
print(min_val[0])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!