[BOJ] 백준 15686 - 치킨 배달

👩🏻‍💻 문제

👩🏻‍💻 정답 코드

from itertools import combinations

n, m = map(int, input().split())

chicken = []
house = []

for i in range(n):
  s = input().split()
  for j in range(n):
    if s[j] == '1':
      house.append((i, j))
    elif s[j] == '2':
      chicken.append((i, j))

result = []
for i in list(combinations(chicken, m)):
    r = 0
    for hy, hx in house:
        dist = []
        for cy, cx in i:
            dist.append(abs(hy-cy)+abs(hx-cx))
        r += min(dist)
    result.append(r)

print(min(result))

처음에는 치킨 거리가 제일 많은 치킨집을 남기는 걸로 해야 하나 했는데 그렇게 했는데도 틀린 경우가 있을 것 같아서 찾아보다가 itertools의 combinations를 써서 중복 없는 조합을 구해 각 경우 중 min 값을 내면 되는 걸 깨달았다. 라이브러리 활용 잘 할 것... 파이썬 정리 한 번 해야겠다

그래서 프로세스는

1. 집, 치킨집 위치를 일단 chicken, house리스트에 저장해두고
2. for i in list(combinations(chicken, m))으로 치킨 가게 중 m개의 조합의 경우의 수를 반복문을 돌아서
3. 한 집씩 차례차례 각 치킨집에 대한 치킨 거리를 구해서 dist 리스트에 저장해놓은 다음
4. 그 중 min 값을 도시의 치킨 거리인 r에 더한다.
5. 모든 집에 대한 치킨 거리가 r에 더해지면 result 리스트에 추가
6. 그렇게 각 치킨집 m개에 대한 조합의 치킨 거리 중 min 값을 프린트

👩🏻‍💻 Remember

from itertools import combinations

for i in list(combinations(chicken, m)):
	...
    for cy, cx in i:
    # m개의 치킨집 조합의 각 치킨집 좌표 반복

라이브러리 잘 외워 두고 적극 활용하기!!!