[백준 15686] 치킨 배달

🍎 [백준 15686] 치킨 배달

문제 링크

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

15686번: 치킨 배달

 

 

⚾ 코드

from itertools import combinations

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

chickens = []
homes = []

for i in range(n):
    for j in range(n):
        if grid[i][j] == 1:
            homes.append([i, j])
        elif grid[i][j] == 2:
            chickens.append([i, j])

chicken_load = n**3
chicken_list = combinations(chickens, m) # 조합을 이용해 치킨 집을 m개 고름

for chicken in chicken_list:
    # chicken -> 치킨집 중 m개 고름
    min_dist = [n*2]*len(homes)
    for i in range(len(homes)):  # 집을 순회하면서
        for a, b in chicken:  # m개의 치킨집과의 거리를 계산.
            if abs(homes[i][0]-a)+abs(homes[i][1]-b) < min_dist[i]:
                min_dist[i] = abs(homes[i][0]-a)+abs(homes[i][1]-b)

    if chicken_load > sum(min_dist): # 각 집의 치킨 거리의 합 = chicken load
        chicken_load = sum(min_dist)

print(chicken_load)

 

 

🔔 해결 과정 & 깨달은 점

- 문제 중에 m개의 치킨 집을 보고 바로 조합을 떠올렸다.

- graph를 순회하면서 집과 치킨 집을 리스트에 저장했다.

- 그리고 m개의 치킨집을 선택하고, 각 집을 순회하면서 치킨집과의 거리 중 최단 거리를 저장했다.

- 각 집을 순회하는 루프가 끝났을 때, 각 집의 치킨 거리를 계산하여, chicken_load보다 짧을 경우 갱신해주었다. 이렇게 되면 최소 치킨 거리가 나온다.