71.피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용)
N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다. 각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호)로 표현됩니다. 행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.
도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다. 집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다. 예를 들어, 도시의 지도가 아래와 같다면
0 1 0 0
0 0 2 1
0 0 1 0
1 2 0 2
(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
내 코드
from itertools import combinations
def dfs():
??
n,m=map(int,input().split())
lst=[list(map(int,input().split())) for _ in range(n)]
pizza_place=[]
for i in range(n):
for j in range(n):
if lst[i][j]==2:
pizza_place.append((i,j))
pizza_select=list(combinations(range(len(pizza_place)),m))
min_dis=int(1e10)
for select in pizza_select:
dis=0
for i in select:
ch=[[0]*n for _ in range(n)]조합으로 모든 경우의 수를 구해서 거리를 구하면 된다는 것은 알았는데, 거리를 구할 때 dx,dy로 시작점에서 모든 좌표로 이동하려고 해서 실패. 거리는 그냥 피자집의 좌표에서 집의 좌표를 빼주면 되는 것이고, 이미 문제에도 나와있는데 생각이 짧았다.
풀이
def DFS(L, s):
global res
if L==m:
sum=0
for j in range(len(hs)):
x1=hs[j][0]
y1=hs[j][1]
dis=2147000000
for x in cb:
x2=pz[x][0]
y2=pz[x][1]
dis=min(dis, abs(x1-x2)+abs(y1-y2))
sum+=dis
if sum<res:
res=sum
else:
for i in range(s, len(pz)):
cb[L]=i
DFS(L+1, i+1)
if __name__=="__main__":
n, m=map(int, input().split())
board=[list(map(int, input().split())) for _ in range(n)]
hs=[]
pz=[]
cb=[0]*m
res=2147000000
for i in range(n):
for j in range(n):
if board[i][j]==1:
hs.append((i, j))
elif board[i][j]==2:
pz.append((i, j))
DFS(0, 0)
print(res)반성점
- 머리가 나쁘면 몸이 고생한다.
배운 것
