[백준 15686번] 치킨 배달 (Python3)

import sys
input = sys.stdin.readline
from collections import deque

N,M = map(int,input().split())

Map = []
house = []
chicken = []

for i in range(N):
  Map.append(list(map(int,input().split())))

for i in range(N):
  for j in range(N):
    if Map[i][j] == 1:
      house.append((i,j))
    elif Map[i][j] == 2:
      chicken.append((i,j))

Nchicken = len(chicken)

housechicken = []
for i in house:
  housechicken.append([])
  for j in chicken:
    yh,xh = i
    yc,xc = j
    housechicken[-1].append(abs(yh-yc)+abs(xh-xc))

delchicken = []

distancecity = 0
for i in housechicken:
  distancecity += min(i)


delcount = Nchicken-M

dq = deque()

def Pick(x):  
  if len(dq) == delcount:
    delchicken.append(tuple(dq))
  for i in range(Nchicken):
    if i > x:
      dq.append(i)
      Pick(i)
      dq.pop()

Pick(-1)

if delcount != 0:
  distancecity = 1000000
  
for delnum in delchicken:
  distancecity_del = 0
  for i in housechicken:
    distance = 100
    for j in range(Nchicken):
      if j in delnum:
        continue
      if i[j] < distance:
        distance = i[j]
    distancecity_del += distance
  distancecity = min(distancecity,distancecity_del)

print(distancecity)

재귀함수를 이용해서 삭제할 치킨집 개수의 조합을 delchicken 리스트에 튜플로 저장하고, 튜플을 불러오는 방법을 사용했다.

 

다른 사람들의 풀이에 비해 코드의 길이가 긴편인데, 다른 사람들의 한 방식을 보니 특별히 다른점은 없는데 한가지 차이점이라면 다른 사람들은 재귀함수가 아닌 itertools라는 아주 편리한 기능을 이용해서 조합을 구했다는 것이었다.

 

비슷한 문제가 나온다면 itertools를 이용해야겠다.

 

 

 

 

오늘의 교훈: itertools 이용하기