[이코테] 구현_치킨 배달 (python) (다시 풀어보기)

문제

나의 풀이

1. 언뜻보면 괜찮지만, but 심각한 문제가..: 실패

# 우선순위 큐를 이용해볼까?
import heapq

n, m = map(int, input().split()) # n: 도시의 길이, m: 가능한 최대 치킨집 갯수
house, store, distance, chick_dist, answer = [], [], [], 0, []

# 도시 분류: 0: 빈칸, 1: 집, 2: 치킨집
for x in range(n):
	city = list(map(int, input().split()))
	for y in range(n):
		# 1이면 집, 2면 가게 list에 추가
		house.append([x, y]) if city[y] == 1 else store.append([x, y]) if city[y] == 2
        
# distance에 가게별 거리를 담음
for s in store:
	for h in house:
		chick_dist += abs(s[0] - h[0]) + abs(s[1] - h[1])
	heapq.heappush(distance, (-chick_dist, store.index(s)))
	chick_dist = 0
    
# 제거해야할 가게 수 만큼 for문
for i in range(len(store) - m):
	# 가장 모든 집까지 거리가 큰 가게를 제거
	dist, chick_index = heapq.heappop(distance)
	store.pop(chick_index)
    
for a in house:
	chick_dist = 1e9
	for b in store:
		# 집에서 가장 가까운 거리의 가게 갱신
		abs_xy = abs(a[0] - b[0]) + abs(a[1] - b[1])
		chick_dist = abs_xy if chick_dist > abs_xy
	answer.append(chick_dist)
print(sum(answer)) # 각 집마다 가게까지의 거리를 모두 더함

: 언뜻보면 좋은 코드(물론 지저분함 ㅎ;)
그러나..
치킨 거리 = 집과 가장 가까운 치킨집 사이의 거리이기 때문에, 설령 어떤 가게에서 모든 집까지의 거리가 다른 가게보다 크다고 할지라도 집들이 모여있는 곳 근처에 존재한다면 1순위로 가까운 가게로 선정될 확률이 큼! 그래서..여기서 오답이 생겨버린다.

그럼 어쩌지?

2. 조합 이용하기: 성공

from itertools import combinations

n, m = map(int, input().split()) # n: 도시의 길이, m: 가능한 최대 치킨집 갯수
house, store = [], []

# 도시 분류: 0: 빈칸, 1: 집, 2: 치킨집
for x in range(n):
	city = list(map(int, input().split()))
	for y in range(n):
		if city[y] > 0: # 1이면 집, 2면 가게 list에 추가
            house.append([x, y]) if city[y] == 1 else store.append([x, y])
            
c_store = list(combinations(store, m)) # 전체 치킨집 중에서 m개를 선택할 조합 list

answer = 1e9
for c in c_store: # 치킨집 조합의 경우를 하나씩 꺼내고
	sum_distance = 0 # 치킨 거리의 합 초기화
	for hx, hy in house: # 각각의 집에 대하여
		distance = 1e9 # 치킨 거리 초기화
		for sx, sy in c: # 치킨 거리 계산: 더 짧은 치킨 거리로 갱신
			distance = min(distance, abs(hx - sx) + abs(hy - sy))
		sum_distance += distance # 치킨 거리의 합 계산
	# 더 짧은 치킨 거리의 합으로 갱신
	answer = min(answer, sum_distance)
    
print(answer)

• 백준: 메모리: 30840KB 시간: 628ms 코드 길이: 1048B

3. 성공..인데 2번이랑 99퍼 같네!?

from itertools import combinations

n, m = map(int, input().split()) # 도시 크기 n * n, 선택한 치킨집 갯수 m

house, chicken = [], [] 
for x in range(n):
    a = list(map(int, input().split()))
    for y in range(n):
        if a[y] == 1:
            house.append((x, y))
        elif a[y] == 2:
            chicken.append((x, y))
            
chicken_list = list(combinations(chicken, m)) # m개의 치킨집 조합 list

answer = 1e9 # m개 치킨집을 골랐을 때 치킨거리: 가장 짧은 거리를 구해야하니까
for chick in chicken_list: # 치킨집 조합 list에서 하나씩 꺼내면서
    dist_total = 0 # 총 치킨거리 초기화
    for h_x, h_y in house: # 각각의 집에 대하여
        dist_one = 1e9 # 치킨집 하나에 대한 치킨거리: 가장 짧은 거리를 구해야하니까
        for c_x, c_y in chick: # 각각의 치킨집에 대하여
            # 해당 치킨집에 대한 치킨거리 구하기
            dist_one = min(dist_one, abs(h_x - c_x) + abs(h_y - c_y))
        dist_total += dist_one # 해당 집의 총 치킨거리 구하기
    answer = min(answer, dist_total) # 전체 가장 짧은 치킨거리 구하기
    print(answer)
print(answer)

다른 사람 풀이(백준)

1. 숏코딩

from itertools import *

[n,m],*l=[[*map(int,o.split())] for o in open(0)]
p=[[],[],[]]
R=range(n)

for i,j in product(R,R): p[l[i][j]]+=[[i,j]]

print(min(sum(min(abs(x-a)+abs(y-b) for a,b in C) for x,y in p[1]) for C in combinations(p[2],m)))

: 뭔가 가독성은 안 좋은것 같지만(숏코딩은 다 그런듯..) 되게되게 짧다..! 나중에 봐야징
: open(), product() 가 뭘까?