[BOJ] 백준 15686번 - 치킨 배달 (python)

문제 바로가기 (백준)

 

완전탐색 문제였고 아직 시간복잡도에 대한 개념이 덜 잡혀있음을 깨달았다.

13Cm의 조합은 100,000을 넘지 않으므로 시간 초과 없이 문제를 해결할 수 있다.

(문제에서 치킨집 개수의 범위를 정해준 것은 분명 이러한 이유가 있었기 때문인 점 기억하기!)

 

13Cm을 파이썬 조합 라이브러리를 이용해 코드를 간결하게 만들 수 있다.

치킨집 중 M개를 고르는 모든 경우에 대해 치킨 거리의 합을 계산하여(완전 탐색) 치킨 거리의 최솟값을 구한다.

 

 

1️⃣ 무한대 표현(INF) : 최단 경로 알고리즘에서 도달할 수 없는 노드에 대한 최단 거리 = 1e9
ex. temp = 1e9

 

2️⃣ 조합(Combination)

from itertools import combinations

# combinations(범위, 개수)
combi = list(combinations(range(1, 4), m))

 

문제 풀이 코드는 다음과 같다. combinations 라이브러리를 썼다면 금방 해결할 수 있는 문제였다.

⭕ 아이디어가 떠오르면 먼저 실행해보고 시간복잡도를 고려해보는 것도 빠른 해결방법이 될 수 있다! ⭕

from itertools import combinations

# input
n, m = map(int, input().split())
house, chicken = [], []
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):
    sum = 0
    for hx, hy in house:
        temp = 1e9
        for cx, cy in candidate:
            temp = min(temp, abs(hx - cx) + abs(hy - cy))
        sum += temp
    return sum

result = 1e9
for candidate in candidates:
    result = min(result, get_sum(candidate))
print(result)