[백준/Python] 15686 치킨 배달

 

최대 M개를 고른다고 해서 처음에는 내가 최대 M개를 선택할 수 있다는 뜻인 줄 알고 그럼 1개, 2개, 3개,···M개 이렇게 다 나눠서 생각을 해야되는건가?! 하고 조금 많이 어렵게 생각했지만, 그게 아니었다는 것을 깨달았다!!!!!!(는 1시간 걸림;

원래 하나에 꽂히면 그 생각에서 벗어나는 데 좀 오래 걸리는 편입니다...

 

암튼 그게 아니라는 걸 깨닫고 한 생각은

1. M개로 combination을 해야겠다!

2. 그러면 치킨집의 위치만 따로 모아둬야겠구나!

3. 어차피 집에서의 거리를 구해야하니까 집이랑 치킨집의 위치를 따로따로 모아야겠다!

이정도였구요, 그래서 코드를 작성하기 시작했습니다~

import itertools

N, M = map(int, input().split())
cityMap = [input().split(' ') for _ in range(N)]
home = []
chicken = []
res = 15000

# 집과 치킨집의 위치를 각각 저장
for i in range(N):
    for j in range(N):
        if cityMap[i][j] == '1':
            home.append([i,j])
        elif cityMap[i][j] == '2':
            chicken.append([i, j])

# M개의 치킨집만 남기고 모두 폐업시키므로, 치킨집 M개가 선택될 수 있는 경우를 모두 구함
chickenComb = list(itertools.combinations(chicken, M))
while chickenComb:
    cc = chickenComb.pop()  # 선택된 M개의 치킨집의 위치
    result = 0  # 각 집에서 선택된 M개의 치킨집 중 최소 거리를 저장하는 변수(최종 치킨거리)
    
    # 집1에서 치킨집1,2...M까지의 거리 중 최솟값을 distances에 저장
    # 집2에서 치킨집1,2...M까지의 거리 중 최솟값을 distances에 저장
    # 위 과정을 집의 개수만큼 진행
    for h in home:
        distances = 150  # 한 집에서 각 치킨집까지의 거리 중 최소 거리를 저장하는 변수
        for i in range(M):
            distances = min(distances, abs(h[0] - cc[i][0]) + abs(h[1] - cc[i][1]))
        result += distances
        
    res = min(result, res)  # 모든 combination들에서 구해진 치킨거리 중 최소를 구함

print(res)

풀이과정

1. home과 chicken이라는 list에 집과 치킨집 각각의 좌표를 저장

2. itertools.combinations를 통해 치킨집 M개가 선택될 수 있는 모든 경우를 저장

3. 한 집에서, 선택된 M개의 치킨집까지의 거리 중 최소 거리를 distances에 담고

4. 그 거리들을 모두 더한 값을 result 저장

    → 여기까지 하면, 한 combination에 대해 치킨거리를 구할 수 있음

5. res는 모든 combination에서 구한 치킨거리 중 최소 값을 의미하며, 이 값을 출력하면 정답

 

상세설명

코드를 간단히 설명하면,

●집 H개, 치킨집 M개, combination한 값 C개라고 할 때,

 

집1에서 치킨집1,2,···M까지 거리 중 최소 = distances 1

집2에서 치킨집1,2,···M까지 거리 중 최소 = distances 2

·

·

·

집H에서 치킨집1,2,···M까지 거리 중 최소 = distances H

distances1 + distances2 + ··· + distances H = result

 

위 과정을 C번 반복하면서 나온 result값 중 최솟값(res)이 정답

 

●여기에서 res는,

위 과정을 통해 result가 나올 때마다 그 전에 res값과 비교해서 min값을 res에 갱신