[백준알고리즘] 15686번: 치킨 배달 -Python

[백준알고리즘] 15686번: 치킨 배달 -Python

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

브루트 포스 방식으로 문제를 풀 수 있었다.

 

모든 집에서 최대 m개의 치킨집을 구성하도록 만든 치킨집들의 조합들까지의 모든 거리를 계산한 후 도시의 치킨 거리를 계산했다.

 

여기서 최대 m개의 치킨집을 만들 때, 기존 치킨집의 수가 m보다 적을 수 있다고 생각을 했고, combinations를 사용해서 모든 조합을 만들었다.

 

아래의 코드로 문제를 풀면 다른 분들에 비해서 시간이 굉장히 많이 소요된다. 이유는 중복의 제거를 안해주었기 때문이다.

A라는 집에서 A'라는 치킨집까지의 거리를 계산할 때, 한 번만 계산하도록 하면 시간이 많이 최적화될 것이다. 하지만, 그 부분은 포함시키지 않고 모든 조합 쌍에서 A' 치킨집이 존재할 때마다, 거리를 계산해주었기 때문에 시간이 많이 소요된다.

 

하지만 케이스가 작기 때문에 시간초과가 발생하지 않고 통과할 수 있다.

from itertools import combinations
from sys import maxsize

n, m = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(n)]
home, chicken = [], []

# 모든 집과 치킨집 위치를 찾음
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            home.append([(i, j), []])
        elif city[i][j] == 2:
            chicken.append((i, j))

m = min(m, len(chicken))
chicken_list = combinations(chicken, m)
ans = maxsize
# 가능한 치킨집 조합 반복
for chicken in chicken_list:
    # 모든 집에서 뽑은 치킨집 조합의 각 치킨집들과의 거리를 계산
    for i in range(len(home)):
        home[i][1] = []
        x1, y1 = home[i][0]
        for j in range(len(chicken)):
            x2, y2 = chicken[j]
            home[i][1].append(abs(x1-x2) + abs(y1-y2))
        dist_list = list(map(lambda x: x[1], home))
    
    # 각 조합에서의 도시의 치킨 거리를 구함
    tmp = 0
    for d in dist_list:
        tmp += min(d)
    ans = min(ans, tmp)
print(ans)

 

20200420

새로 푼 방법으로는 위에서 언급했듯이 중복의 제거를 해서 통과할 수 있었다. 하나의 집에서 모든 치킨집까지의 거리를 미리 다 계산을 해놓은 뒤, 치킨집을 선택하는 조합에 맞게 각 거리를 사용한다.

 

각 집에서 모든 치킨집까지의 거리를 구한 뒤, 조합으로 선택된 치킨집들 중에서 거리가 가장 짧은 거리를 구한다. 모든 집에 마찬가지 처리를 해주게 되면 도시의 치킨 거리가 된다.

from itertools import combinations

n, m = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(n)]
chicken = []
home = []
chicken_distance = []

for i in range(n):
    for j in range(n):
        if city[i][j] == 2:
            chicken.append((i, j))
        elif city[i][j] == 1:
            home.append((i, j))

for i, (hi, hj) in enumerate(home):
    chicken_distance.append([0] * len(chicken))
    for j, (ci, cj) in enumerate(chicken):
        chicken_distance[i][j] = abs(ci-hi) + abs(cj-hj)

if len(chicken) <= m:
    print(sum(map(lambda x: min(x), chicken_distance)))
    exit()

ans = 20202020
chicken_idx = combinations(range(len(chicken)), m)
for ci in chicken_idx:
    distance = 0
    for h in range(len(home)):
        tmp = 20202020
        for i in ci:
            tmp = min(tmp, chicken_distance[h][i])
        distance += tmp
    ans = min(ans, distance)
print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다