[백준] 15686 - 치킨 배달

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

15686번: 치킨 배달

문제 한줄 이해

- N*N인 도시가 있을때 0 은 빈칸 1은 집 2 는 치킨집으로 이루어져 있을 때 m개의 치킨집을 골라 모든 집에서의 치킨 거리가 가장 짧은 경우를 구하기

생각난 풀이

1번째 방법: 백트래킹이 떠올랐다. 주어진 치킨집 중에서 m개를 골라야하기 때문이다.

이때 거리라는 것은 (x1,y1), (x2,y2)가 있을 때 가장 가깝다는 것은 |x1-x2| + |y1-y2|의 값이 제일 작은 경우가 가장 작은 가까운 경우이다.

이를 가지고 처음에 입력받은 치킨집과 집의 좌표를 담아두고 백트래킹을 통해 골라진 치킨들과의 거리를 구한다.

import sys
from collections import deque
n, m = map(int,sys.stdin.readline().split())

# 도시정보
chicken = []
for i in range(n):
    chicken.append(list(map(int,sys.stdin.readline().split())))

# 집과 치킨집의 좌표를 담아두기
homes =[]
chicks =[]
for i in range(n):
    for j in range(n):
        if chicken[i][j] == 1:
            homes.append([i,j]) 
        if chicken[i][j] == 2:
            chicks.append([i,j])

def back(start):
    global result
    if len(select) == m:
        # m개의 치킨집이 다 골라지면 거리 계산하기
        sums = 0
        for r1,c1 in homes:
            now=abs(r1-select[0][0]) + abs(c1-select[0][1])
            for r2,c2 in select:
                if now > abs(r1-r2) + abs(c1-c2):
                    now = abs(r1-r2) + abs(c1-c2)
            sums += now
        if sums < result:
            result = sums
        return
    
    for i in range(start,len(chicks)):
        select.append(chicks[i])
        back(i+1)
        select.pop()

result = 1e9
select = []
back(0)
print(result)