[백준] 15686 파이썬

문제

---

• 백준 15686 (골드 5)

백준 15686

2차원 배열로 집의 위치와 치킨집의 위치가 주어질 때, 집과 치킨집 간의 거리 합인 “도시 치킨 거리”를 최소로 하면서 적절하게 m개의 치킨집만 남기고 나머지를 폐업시켜야하는 문제였다.
m개를 제외하고 치킨집을 폐업시킨다니 안타까운 문제였다.

내 코드

---

얼마전에 풀었던 문제였다.
그때 문제를 풀 때, 시간초과 때문에 꽤나 고생을 했던 것이 기억이 나서 쉽게 해결할 수 있었다.
집과 치킨집의 위치를 따로 리스트에 저장해두고 백트래킹을 돌면서 치킨집 중 m개를 골라서 거리를 계산하면서 최소값을 갱신하는 방식으로 구현하였다.

import sys
input = sys.stdin.readline

n, m = map(int,input().split())
house = []
chicken = []
for i in range(n):
    temp = list(map(int,input().split()))
    for j in range(n):
        if temp[j] == 1:
            house.append((i,j))
        elif temp[j]==2:
            chicken.append((i,j))

visited = [False]*len(chicken)
minimun = 10**9 

def back(index,cnt):
    global minimun
    if cnt==m:
        clen = 0
        for i in house:
            cmin = 10**9 
            for j in range(len(visited)):
                if visited[j]:
                    distance = abs(i[0]-chicken[j][0])+abs(i[1]-chicken[j][1])
                    cmin = min(cmin, distance)
            clen += cmin
        minimun = min(minimun, clen)
        return

    for i in range(index, len(chicken)):
        if not visited[i]:
            visited[i] = True
            back(i+1,cnt+1)
            visited[i]=False

back(0,0)
print(minimun)