백준 알고리즘 15686번: 치킨 배달 (Python)

문제 정보

---

15686번: 치킨 배달

 

 

핵심

---

모든 치킨집들 중 M개의 치킨집을 갖는 부분집합들을 구해서, 각 집까지의 최소 치킨 거리를 갖는 부분집합을 구하기

 

 

풀이

---

from sys import stdin
from itertools import combinations

N, M = map(int, stdin.readline().split())

house = []
chicken = []

for i in range(N):
    row = list(map(int, stdin.readline().split()))
    for j in range(N):
        if row[j] == 1:
            house.append((i, j))
        elif row[j] == 2:
            chicken.append((i, j))

answer = []

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

for chicken_combination in combinations(chicken, M):
    ck_distance = 0
    for r2, c2 in house:
        tmp_distance = float('inf')
        for i in range(M):
            r1, c1 = chicken_combination[i]
            tmp_distance = min(tmp_distance, distance(r1, c1, r2, c2))
        ck_distance += tmp_distance
    answer.append(ck_distance)
print(min(answer))

먼저, 모든 좌표를 검사해서 치킨집과 집이 위치한 좌표를 각각의 배열에 집어넣음

그 후, combinations 라이브러리를 사용하여 모든 치킨집들 중 M개의 치킨집을 갖는 부분집합을 구하고

해당 부분집합에 속하는 M개의 치킨집 - 집 간의 최소 치킨거리를 각각의 집합마다 구한다

그리고 그 최소 치킨 거리들 중 가장 작은 값이 될 때, 최소 치킨 거리가 된다

 

 

고찰

---

최대한 DFS, 백트래킹을 사용하여 문제를 풀이하고자 하였는데 내 능력 부족으로 풀이하지 못했다

이 부분은 더욱 열심히 공부해서, 관련 문제들을 많이 풀어보고 보완하고자 노력하겠다

또한 이 문제를 이해하는 데에 있어서 많은 시간이 소요되었는데, 열심히 노력해서 더 빠르게 문제를 이해할 수 있는 능력을 길러야 할 것 같다

 

 

참고

---

GitHub - dduneon/CodingTestPy