치킨 배달

문제 설명

https://www.acmicpc.net/problem/15686
<입력>
<출력>
<예시>
5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2
5

5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2
10

5 1
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
11

---

나의 풀이

29452 KB / 860 ms

from itertools import combinations

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

house_sets = []
chicken_sets = []

def chicken_abs(house, chicken):
    return abs(house[0] - chicken[0]) + abs(house[1] - chicken[1])


for i in range(n):
    for j in range(n):
        if map_info[i][j] == 1:
            house_sets.append((i, j))
        elif map_info[i][j] == 2:
            chicken_sets.append((i, j))

combination_of_chicken_sets = list(combinations(chicken_sets, m))
print(combination_of_chicken_sets)

result = [0 for _ in range(len(combination_of_chicken_sets))]
for i in range(len(combination_of_chicken_sets)):
    temp = 9999
    temp_result = 0
    for j in range(len(house_sets)):
        for k in range(m):
            temp = min(temp, chicken_abs(house_sets[j], combination_of_chicken_sets[i][k]))
        temp_result += temp
        temp = 9999
    result[i] += temp_result
print(min(result))

---

책 풀이

29452 KB / 484 ms

from itertools import combinations

n, m = map(int, input().split())
chicken, house = [], []

for r in range(n):
    data = list(map(int, input().split()))
    for c in range(n):
        if data[c] == 1:
            house.append((r, c)) # 일반 집
        elif data[c] == 2:
            chicken.append((r, c)) # 치킨집

# 모든 치킨 집 중에서 m개의 치킨 집을 뽑는 조합 계산
candidates = list(combinations(chicken, m))

# 치킨 거리의 합을 계산하는 함수
def get_sum(candidate):
    result = 0
    # 모든 집에 대하여
    for hx, hy in house:
        # 가장 가까운 치킨 집을 찾기
        temp = 1e9
        for cx, cy in candidate:
            temp = min(temp, abs(hx - cx) + abs(hy - cy))
        # 가장 가까운 치킨 집까지의 거리를 더하기
        result += temp
    # 치킨 거리의 합 반환
    return result

# 치킨 거리의 합의 최소를 찾아 출력
result = 1e9
for candidate in candidates:
    result = min(result, get_sum(candidate))

print(result)

---

다른 사람 풀이

29200 KB / 112 ms

from sys import stdin
from itertools import combinations as comb
r = stdin.readline

n,m = map(int, r().strip().split())
city = [r().strip().split() for i in range(n)]
ans = 1e9
houses = []
chickens = []
for i in range(n):
    for j in range(n):
        if city[i][j] == '1':
            houses.append((i,j))
        elif city[i][j] == '2':
            chickens.append((i,j))

dists = [list(map(lambda x : abs(x[0]-c[0]) + abs(x[1]-c[1]), houses)) for c in chickens]
for co in comb((i for i in range(len(chickens))), m):
    res = sum(map(min, zip(*[dists[i] for i in co])))


    if res < ans:
        ans = res
print(ans)

느낀 점

왜 이렇게 시간 효율 차이가 많이 날까? 비교해보자