[백준 15686] 치킨배달(파이썬)

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

15686번: 치킨 배달

치킨집 중

가장 최대 지점이 되는

M개를 고르는 문제입니다.

이 문제는 그리디로 풀 수도 있지만

만약 그리디를 선택하시게 된다면

시간초과로 막히는 경우가 발생할 것입니다.

저 문제같은 경우에는

수 많은 치킨집들 중

M개를 조합해서 만들어야하므로

M의 숫자가 커지면 커질수록

경우의 수가 늘어납니다.

ABCDE 5개가 있고

M이 3일 경우에

ABC

ABD

ABE

ACD

ADE

.......

경우가 정말 많아지게 되고

이걸 다 그리디로 구한다?

특히나 이걸 DFS로 구한다치면

바로 시간초과가 발생해서

나는 맞았는데

왜 시간초가가 뜰까

하는 고민만 가지게 됩니다.

그래서 이 문제같은 경우엔

combination을 사용하면

그런 고민없이 풀리게 되는 문제입니다.

 

# 백준 15686 치킨배달
from itertools import combinations

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
house = []
chicken = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            house.append([i, j])
        if graph[i][j] == 2:
            chicken.append([i, j])
# print(house)
# print(chicken)
able = M
possible_chicken = []

for c in list(combinations(chicken, able)):
    possible_chicken.append(c)
# print(possible_chicken)

mi_ch = 1e9

for c in possible_chicken:
    # print(c)
    gather = []
    for ho in house:
        dp = []
        for chick in c:
            dp.append(abs(ho[0] - chick[0]) + abs(ho[1] - chick[1]))
        gather.append(min(dp))

    # print(sum(gather))
    mi_ch = min(mi_ch, sum(gather))
print(mi_ch)

 

이 문제는 제가 예전에

비슷한 문제를 풀다가

하도 시간초과가 떠서 고생하다가

솔루션을 보니

combination하나면 풀 수 있는 문제가 생각나서

쉽게 구할 수 있었습니다.

알고리즘 문제는 풀다보면 반복된다는 게

이런 건가 싶기도 하네요.

만약 여러분들이 경우를 구하다가

너무 많은 경우들이 구해진다

라는 생각이 들게되면은

combination도 떠올리면 좋겠네요.