15686 치킨 배달 (python)

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

15686번: 치킨 배달

 

 

 

 

 

문제 접근

각 치킨집에서 집까지 거리를 BFS로 풀고있었다.

다적고나니 BFS로 풀 필요가 없고 그냥 구할 수 있었다는걸 알았다...

치킨집과 일반 집의 위치를 찾고, 각 거리를 구했다.

그리고 거리들에서 치킨집중 M개만큼 뽑아서 그 중 최소값들을 더한게 도시의 치킨 거리다.

 

약간의 깡 구현이 있었는 듯

from itertools import combinations는 쓰지않았다.

쓰면 코드가 더 간결하긴 한데 조합같은건 import보단 구현해보는 재미가 더 있는듯

 

 

 

 

 

코드

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


"""
1위치와 2위치를 기록
각 차이를 새 배열에 저장
배열에서 조합 m개 뽑기
"""

N, M = map(int,input().split())
arr = []
for i in range(N):
    arr.append(list(map(int,input().split())))

pos1 = []
pos2 = []
for i in range(N):
    for j in range(N):
        if arr[i][j]==1:
            pos1.append((i,j))
        elif arr[i][j]==2:
            pos2.append((i,j))

dis = []
for x2, y2 in pos2:
  t_dis = []
  for x1, y1 in pos1:
      t_dis.append(abs(x2-x1) + abs(y2-y1))
  dis.append(t_dis)

stack = []
ans = 99999
len1 = len(pos1)
len2 = len(pos2)

def rec(cur, cnt):
    if cnt == M:
        t_ans = 0
        for i in range(len1):
            t_min = []
            for j in range(M):
                t_min.append(dis[stack[j]][i])
            t_ans += min(t_min)
        global ans
        ans = min(t_ans, ans)
        return

    for i in range(cur, len2):
        stack.append(i)
        rec(i+1, cnt+1)
        stack.pop()
 
rec(0, 0)
print(ans)