[DFS 활용] - 피자 배달 거리

피자 배달 거리

 

N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다.

각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다.

각 격자칸은 좌표(행번호, 열 번호) 로 표현됩니다.

행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.
도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재 하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.

집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다. 예를 들어, 도시의 지도가 아래와 같다면

 

(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다.

최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다.

도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.
시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다.

도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.

 

▣ 입력설명
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다. 둘째 줄부터 도시 정보가 입력된다.

▣ 출력설명
첫째 줄에 M개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다.

 

▣ 입력예제 1

4 4
0 1 2 0

1 0 2 1

0 2 1 2

2 0 1 2

▣ 출력예제 1

6

 

나의 코드 1 DFS

def DFS(L,s):
    global Minn
    if L==m:
        S=0
        for i in range(len(h)):
            
            Minnn=10000
            x,y=h[i]
            for j in res:
                temp2=abs(x-p[j][0]) +abs(y-p[j][1]) 
                if Minnn>temp2:
                    Minnn=temp2
            S=S+Minnn
        if S<Minn:
            Minn=S
        
    else:
        for i in range(s,PCount):
            res[L]=i
            DFS(L+1,i+1)


n,m=map(int,input().split())

arr=[list(map(int,input().split())) for _ in range(n)]
h=[]
p=[]
Minn=10000
for i in range(n):
    for j in range(n):
        if arr[i][j]==1:
            h.append([i,j])
        if arr[i][j]==2:
            p.append([i,j])

PCount=len(p)
res=[0]*(m)
DFS(0,0)

print(Minn)



# from itertools import combinations
# arr=[[1,2],[2,3],[3,4]]
# print(list(combinations(arr,2)))

 

 

나의 코드 1 조합  라이브러리

from itertools import combinations
n,m=map(int,input().split())

arr=[list(map(int,input().split())) for _ in range(n)]
h=[]
p=[]
Minn=10000
for i in range(n):
    for j in range(n):
        if arr[i][j]==1:
            h.append([i,j])
        if arr[i][j]==2:
            p.append([i,j])

res=list(combinations(p,m))



for x in res:
    S=0
    for i in range(len(h)):
        Minnn=10000
        hx,hy=h[i]
        for k in range(m):
            temp2=abs(hx-x[k][0]) +abs(hy-x[k][1])
            if Minnn>temp2:
                Minnn=temp2
        S=S+Minnn
    if S<Minn:
        Minn=S

print(Minn)

 

 

문제를 읽고 이해하는게 시간이 꾀나 걸렸다.

'도시'의 피자 배달 거리와 '집들의'피자 거리의 개념이 헷갈려 몇번이나 읽었다 !!

 

문제를 대충읽지 말고 천천히 이해하면서 읽는 습관을 들여야겠다..!!