[백준 파이썬] 15686 치킨 배달

[백준 파이썬] 15686 치킨 배달

문제유형 

• 브루트포스 알고리즘
• 백트래킹
• 구현

 

문제

크기가 N x N인 도시가 있다. 도시는 1x1 크기의 칸으로 나누어져 있다 

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

위와 같이 입력이 주어지는데 이때 r행 c열에 위치한 지점을 (r,c)와 같은 형태로 나타낸다.

r, c는 1부터 시작한다. 이때 0은 비칸, 1은 집 , 2는 치킨집이다.

 

자신의 집에서 가장 가까운 치킨집 과의 거리를 치킨 거리라 한다.

각각의 집은 치킨 거리를 가지고 있으며 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

 

치킨 거리를 구하는 방법은 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

 

치킨집 중 M개를 골라 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

 

입력

첫 줄에 N과 M이 주어진다

둘째 줄부터는 N개의 도시의 정보가 주어진다.

출력

치킨집 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

풀이

일단 난 주어진 도시의 정보로부터 집과 치킨집의 좌표를 구해 각각 배열로 저장하였다.

그 후 각 집으로부터 모든 치킨집과의 거리를 구한다.

a=len(house)
#치킨 거리 저장하기 위한 리스트
chick_d=[[] for i in range(a)]

for x1,y1 in chick:
    count=0
    for x2,y2 in house:
        ans=abs(x2-x1)+abs(y2-y1)
        chick_d[count].append(ans)
        count+=1

 

chick_d 배열은 2차원 배열로 chick_d [0]은 첫 번째 집으로부터 모든 치킨집과의 거리를 저장한다.

 (chick_d [0][0]은 처번째 집에서 chick에 저장된 첫 번째 치킨집과의 거리이다.)

 

이렇게 모든 치킨집과의 거리를 구했으면 이제 M개의 치킨집을 뽑아야 한다 나는 combinations를 사용하여

M개의 치킨집을 뽑는 모든 경우수를 리스트로 반환하여 FOR문을 돌렸다.

각 집에서 뽑힌 M개의 치킨집과 거리가 가장 작은 걸 고른다  그렇게 뽑힌 각 집에서 가장 작은 거리의 합을 저장한다.

그 후 다시 M개의 치킨집을 뽑는 경우수를 실행하여  위의 과정을 반복하여 앞에서 구한 합과 비교하여 가장 작은 합을 구한다.

 

최종적으로 이렇게 구한 합을 출력한다.

코드

from itertools import combinations
n,m=map(int,input().split())
array=list(list(map(int,input().split())) for i in range(n))

house=[]
chick=[]
for i in range(n):
    for j in range(n):
        if array[i][j]==1:
            house.append([i+1,j+1])
        if array[i][j]==2:
            chick.append([i+1,j+1])


a=len(house)
#치킨 거리 저장하기 위한 리스트
chick_d=[[] for i in range(a)]

for x1,y1 in chick:
    count=0
    for x2,y2 in house:
        ans=abs(x2-x1)+abs(y2-y1)
        chick_d[count].append(ans)
        count+=1

sum=9999999999999999999

for x in list(combinations(range(len(chick)),m)):
    sum_ans=0
    for i in range(len(house)):
        min_value=99999999999999999999999999
        for j in x:
            min_value=min(min_value,chick_d[i][j])

        sum_ans+=min_value
    
    sum=min(sum,sum_ans)
print(sum)