오늘도 !!! 순도 100%짜리의 내 풀이 ~~~ ❤️‍🔥

1. 내 풀이 - 성공

import sys
from itertools import combinations
input = sys.stdin.readline

n, m = map(int, input().split())
city = []
distance = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(n):
    city.append(list(map(int, input().split())))

chickens =  []
for i in range(n):
    for j in range(n):
        if city[i][j] == 2:
            chickens.append([i, j])

all_distance = []
for comb in combinations(chickens, m):
    for i in range(n):
        for j in range(n):
            if city[i][j] == 1:
                temp = 0
                minDistance = (n-1)*2
                for chicken in comb:
                    temp = abs(i-chicken[0]) + abs(j-chicken[1])
                    minDistance = min(temp, minDistance)
                    distance[i][j] = minDistance
    total = 0
    for i in range(n):
        total += sum(distance[i])
    all_distance.append(total)


print(min(all_distance))

예전에 좀 어려워보여서 넘긴 문젠데 !!! 해결했다 😎
처음에는 문제 이해가 제대로 안돼서 계속해서 생각했다 ,,,

포인트는 일단은 치킨집 M개를 생각하자! 는 것 같다.

n, m = map(int, input().split())
city = []
distance = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(n):
    city.append(list(map(int, input().split())))

일단 먼저 n과 m을 받아주고, for문을 통해서 city의 치킨집 정보와 집 정보를 받아온다. 그리고 각 치킨집에 대한 집들의 최소 거리를 저장하기 위해 city와 크기가 같고 0으로 초기화된 이중 리스트인 distance 를 만들어준다.

chickens =  []
for i in range(n):
    for j in range(n):
        if city[i][j] == 2:
            chickens.append([i, j])

다음은 치킨집에 대한 정보를 따로 저장해야 한다. 이중 반복문을 돌면서 치킨집이면 chickens에 좌표 형태로 저장한다. 좌표 형태로 저장하는 이유는 추후에 이를 combination 해서 여러 경우의 수를 저장하도록 할 것이고, 그럴 경우에 좌표 형태가 편하기 때문이다.

all_distance = []
for comb in combinations(chickens, m):
    for i in range(n):
        for j in range(n):
            if city[i][j] == 1:
                temp = 0
                minDistance = (n-1)*2
                for chicken in comb:
                    temp = abs(i-chicken[0]) + abs(j-chicken[1])
                    minDistance = min(temp, minDistance)
                    distance[i][j] = minDistance
    total = 0
    for i in range(n):
        total += sum(distance[i])
    all_distance.append(total)

다음은 도시들을 탐험하며 한 집에서 어떤 치킨집이 가장 가까운지 그 거리를 구하는 코드이다. 일단 치킨집에 대한 여러 combination에 의해 다양한 distance 값이 나올 수 있으므로 all_distance라는 리스트를 만들어준다.

그 후에는 살아남을 치킨집 후보군을 itertool의 combination을 이용해서 구해준다. 예를 들어 5개의 치킨집 중 2개의 치킨집만 고른다면 총 10개의 경우의 수가 나오게 되는 것이다. 여기서 comb에는 후보 치킨집들이 좌표 형태로 저장되어 있을 것이다.

그리고 마을 전체를 돌면서 어떤 위치에 집이 있으면 (1일 때), 일단 거리를 계산해주기 위한 temp 변수와 거리의 최댓값인 minDistance를 초기화해준다. 그리고 그 집에서 (지금 if문에 걸린 집) 각 치킨집에 대한 거리를 구해준다. comb에는 여러 개의 치킨집이 있으므로 (5개의 치킨집 중 2개를 골랐다면, 2개가 들어있을 것) 이를 또 for문을 사용해서 한 치킨집 당의 거리를 구해준다. 그리고 minDistance와 temp(현재 계산 중인 치킨집과 집까지의 거리)를 비교하여 더 적은 수를 다시 minDistance에 넣고, 이를 distance[i][j]에 저장해준다.

이렇게 모든 마을을 돌게 되면, 모든 집들이 치킨집 후보군들에 대한 최소 거리가 계산되었을 것이고, 그 값들은 모두 distance에 저장이 되어 있을 것이다. 그러면 이제 이 distance에 들어있는 값들을 더해서 all_distance에 추가해준다. 치킨집 후보군에 따른 거리가 다양할테니 말이다.

print(min(all_distance))

이제 그 중 최솟값만 뽑아내면 끝!

2. 다른 풀이 - 백트래킹

n, m = map(int, input().split())
answer = float('inf')
​
house, chicken = [], []
​
for i in range(n):
    row = list(map(int, input().split()))
    for j in range(n):
        if row[j] == 1:
            house.append((i, j))
        elif row[j] == 2:
            chicken.append((i, j))
​
​
def dfs(idx, cnt):
    global answer, chicken, m
    if idx > len(chicken):
        return
    if cnt == m:
        total_distance = 0
        for r1, c1 in house:
            distance = float('inf')
            for i, pos in enumerate(chicken):
                if checked[i]:
                    r2, c2 = pos
                    distance = min(distance, abs(r1 - r2) + abs(c1 - c2))
            total_distance += distance
        answer = min(answer, total_distance)
    
    checked[idx] = True
    dfs(idx + 1, cnt + 1)
    checked[idx] = False
​
​
​
checked = [False] * (len(chicken) + 1)
dfs(0, 0)
​
print(answer)

풀이 출처: https://alreadyusedadress.tistory.com/323

예전에 DFS 풀 때 이 문제를 보고 ... 풀었는데 ... 답을 봐도 아직 크게 와닿지는 않는다 ...! 다음에 분석해봐야지.

3. 마치며

즐거운 ~~~ 행복한 !!! 알고리즘 끝!