[백준 15686번] 치킨 배달

15686번: 치킨 배달

import itertools

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

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

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

chicken_house_list = set()
house_list = set()

min_value = float("inf")

for i in range(n):
    for j in range(n):
        if input_city[i][j] == 2:
            chicken_house_list.add((i,j))
        elif input_city[i][j] == 1:
            house_list.add((i,j))

combination_list = set(itertools.combinations(chicken_house_list,m))

for combination in combination_list:
    distance = [float("inf") for _ in range(len(house_list))]
    for i, value in enumerate(house_list):
        hx, hy = value[0], value[1]
        for cx, cy in combination:
            distance[i] = min(distance[i], calculate_distance(hx,hy,cx,cy))
    if min_value > sum(distance):
        min_value = sum(distance)

print(min_value)

이번 문제는 M개의 치킨집을 임의로 선택했을 때, 각 집에서 치킨집까지의 거리의 합의 최소값을 구하는 문제이다.

 

이 문제는 여러 개의 치킨집중에서 M개를 선택하여 모든 경우의 수를 따져보아야 하기 때문에 조합을 활용한 완전탐색(Brute-Force) 문제라고 할 수 있다.

 

따라서 치킨 거리 계산을 해주기 위한 함수(calcuate_distance)를 선언하였고, itertools 라이브러리를 import하여 itertools.combinatons()를 사용해 M개의 모든 치킨집에 경우의 수를 구해주었다.

(참고로, 치킨 집의 개수는 13개 이하로 한정되어 있기 때문에 완전탐색을 하더라도 시간초과가 발생하지 않는다.)

 

하지만 처음에 제출하였을 때는 시간초과가 발생하였는데, 문제에서 주어진 명세대로 치킨 거리를 구하지 않고 BFS를 사용하여 치킨 거리를 구했기 때문이었다.

 

따라서 BFS가 아닌 주어진 명세대로 치킨 거리를 구하였고, 완전탐색을 통해 최소 값을 구한 결과 시간초과 없이 문제를 해결할 수 있었다.

 

배운 점 및 느낀 점

1. 최단 거리가 나왔다고 해서 무작정 BFS로 풀려고 하지말고, 문제에서 주어진 명세를 제대로 읽고 활용하자.
2. 완전탐색(Brute-Force) 문제를 많이 풀어보도록 하자.