[BAEKJOON] 15686번. 치킨 배달

 

 

https://www.acmicpc.net/problem/15686 - 15686. 치킨 배달

이번엔 내가 직접 써보면서 공부. 앞서 봤던 기출에 비해 상당히 쉬운 편인 듯.

 

---

 

'''
1. 치킨집 조합 구하기 (최대 m개)
2. 각 치킨집 조합의 좌표들과 가장 가까운 집 사이의 거리 구하기
2-1. 각 치킨집 조합 1개씩
2-2. 각 조합 내 치킨집 좌표들과 집 사이의 거리 중 최솟값 구하기
3. 도시의 치킨 거리 최솟값 구하기
'''

def make_combination(select_xy, start=0):
    if len(select_xy) == m:
        combination.append(select_xy)
        return
    
    for i in range(start, len(chickens)):
        if not visited[i]:
            visited[i] = True
            make_combination(select_xy + [chickens[i]], i+1)
            visited[i] = False


n, m = map(int, input().split())     # n: 도시 크기, m: 남길 치킨집
town = [list(map(int, input().split())) for _ in range(n)]

chickens = []
houses = []

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

combination = []        # 남길 치킨집 조합 구하기
visited = [False for _ in range(len(chickens))]
make_combination([])

ans = float('inf')
for loc in combination:
    total = 0       # 총 치킨집 조합과 가까운 집 사이의 거리 합
    for home in houses:
        min_val = float('inf')     # 치킨집:가까운 집 = 1:1
        for l in loc:
            tmp = abs(l[0] - home[0]) + abs(l[1] - home[1])
            if tmp < min_val:
                min_val = tmp
        total += min_val
    if total < ans:
        ans = total

print(ans)

make_combination() 함수 내에서, 조합을 생성할 때 중복되는 원소가 생기지 않도록 항상 반복의 시작을 start로 설정
=> for i in range(start, len(chickens)):

visited 리스트는 길이가 치킨집의 총 수와 같게 생성하기 => visited = [False for _ in range(len(chickens))]

★ 첫 번째 치킨집 조합과 가까운 집 사이의 거리를 구할 때:  → 계속 헷갈렸던 부분
1) homes 내의 집과 조합 내의 치킨집 좌표의 거리를 하나씩 계산 => 조합의 최소 거리인 min_val와 비교해서, 더 작으면 새롭게 설정
2) 조합 내 치킨집과 가장 가까운 집 사이의 총 거리 수 구하기 => total
3) total과 answer 비교해서 더 작은 수를 answer로 재설정