백준 15686번: 치킨 배달 파이썬 코드(백트래킹)

https://upload.wikimedia.org/wikipedia/commons/thumb/c/c3/Python-logo-notext.svg/600px-Python-logo-notext.svg.png

import sys
from itertools import combinations

n,m = map(int, sys.stdin.readline().split())

home = []
chicken = []

for i in range(n):
    a = list(map(int, sys.stdin.readline().split()))
    for j in range(n):
        if a[j] == 1:
            home.append([i+1,j+1])
        elif a[j] == 2:
            chicken.append([i+1,j+1])

INF = sys.maxsize

temp = []
dislist = []

for k in combinations(chicken, m):
    distance = [INF for _ in range(len(home))]
    for i in range(len(home)):
        for bhc in k:
            if int(abs(home[i][0] - bhc[0]) + abs(home[i][1] - bhc[1])) < distance[i]:
                distance[i] = abs(home[i][0] - bhc[0]) + abs(home[i][1] - bhc[1])
    dislist.append(sum(distance))

print(min(dislist))

설명

n,m을 입력받고 도시의 정보를 입력받을 때, 2차원 리스트로 받지않고 집과 치킨집을 분리하여 빈칸을 제외하고 입력을 받는다.

거리의 최소값을 구하는 문제이므로, INF(infinite)를 distance에 집의 개수만큼 채워준다.

이 문제는 브루트포스 문제이기 때문에 콤비네이션 함수를 통해 치킨집 중에 m개를 뽑아 거리가 가장 적은 것을 전부 비교해가며 뽑는다.

3중 for문을 사용하였다.

 

문제점

백트래킹으로 콤비네이션을 대체하려하였으나, 시간초과가 생겨서 콤비네이션함수를 사용하였다.