https://www.acmicpc.net/problem/15686
15686번: 치킨 배달크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸www.acmicpc.net
처음에 bfs를생각했는데 더 간단한 풀이가 있었다.
모든 집과 치킨집을 구해놓고,
치킨집에 대한 원소가m개인 combination을 구하고,
각 combination에 대하여 치킨 거리를 구해 비교한다.
import sysfrom itertools import combinationsinput=sys.stdin.readline
n,m=map(int,input().split())arr=[]chickenhouse=[]blank=[]for i in range(n):
tmp=list(map(int,input().split())) for j in range(n):
if tmp[j]==1: blank.append((i,j)) elif tmp[j]==2:
chickenhouse.append((i,j))chicken_comb=combinations(chickenhouse,m)
answer=1e+7for chickens in chicken_comb: dist=0 for i,j in blank:
dist+=min([abs(i-c[0])+abs(j-c[1]) for c in chickens])
if dist>=answer:break answer=min(answer,dist)print(answer)