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
dis가 무한루프로 나온다 원인이 무엇일까
def dfs(x):
global dis
if x==m:
res.append(dis)
else :
for i in range(len(pizza)) :
for j in range(len(house)) :
if ch[i]==0:
dis+=abs(pizza[i][0]-house[j][0])+abs(pizza[i][1]-house[j][1])
ch[i]=1
dfs(x+1)
ch[i]=0
dis-=abs(pizza[i][0]-house[j][0])+abs(pizza[i][1]-house[j][1])
if __name__=='__main__' :
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
pizza=[]
house=[]
for i in range(n):
for j in range(n):
if a[i][j]==2:
pizza.append((i,j))
elif a[i][j]==1:
house.append((i,j))
ch=[0]*len(pizza)
dis=0
res=[]
dfs(0)
print(min(dis))
(2) 조합 개념 추가했는데도 무한루프가 돈다 왜일까?
#==> dis+=k / dfs호출 / dis 전 상태로 복구 부분의 인덴트를 잘못 설정
def dfs(x,s):
global dis
if x>m:
return
if x==m:
print(dis)
return
else :
for i in range(s,len(pizza)):
for j in range(len(house)):
k=abs(pizza[i][0]-house[j][0])+abs(pizza[i][1]-house[j][1])
dis+=k
dfs(x+1,s+1)
dis-=k
if __name__=='__main__' :
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
pizza=[]
house=[]
for i in range(n):
for j in range(n):
if a[i][j]==2:
pizza.append((i,j))
elif a[i][j]==1:
house.append((i,j))
dis=0
dfs(0,0)
(3) 인덴트 재 설정 => 그럼에도 정답보다 작은 숫자들 존재하는데 이는 s가 커서 적게만 더해진 애들로 추정, 얘네를 어떻게 없애지?
====>+ 조합에서 dfs갱신할 때 dfs(x+1, i+1) 이다.. dfs(x+1,s+1)아니구..
def dfs(x,s):
global dis
if x>m:
return
if x==m:
print(x,dis, end=' ')
print()
return
else :
for i in range(s,len(pizza)):
for j in range(len(house)):
k=abs(pizza[i][0]-house[j][0])+abs(pizza[i][1]-house[j][1])
dis+=k
dfs(x+1,s+1)
dis-=k
cnt-=1
if __name__=='__main__' :
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
pizza=[]
house=[]
for i in range(n):
for j in range(n):
if a[i][j]==2:
pizza.append((i,j))
elif a[i][j]==1:
house.append((i,j))
dis=0
dfs(0,0)
(4) i+1로 수정해도 약간 핀트가 안 맞는데가 있는데 그 부분을 못 찾고 있음
def dfs(x,s):
global dis
if x==m:
print(x,dis, end=' ')
print()
res.append(dis)
return
else :
for i in range(s,len(pizza)):
for j in range(len(house)):
k=abs(pizza[i][0]-house[j][0])+abs(pizza[i][1]-house[j][1])
dis+=k
dfs(x+1,i+1)
dis-=k
if __name__=='__main__' :
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
pizza=[]
house=[]
for i in range(n):
for j in range(n):
if a[i][j]==2:
pizza.append((i,j))
elif a[i][j]==1:
house.append((i,j))
dis=0
res=[]
dfs(0,0)
print(min(res))
def dfs(x,s):
global res
if x==m:
sum=0 #도시와 피자의 거리
for j in range(len(house)):
x1=house[j][0]
y1=house[j][1]
dis=10000
for x in cb:
x2=pizza[x][0]
y2=pizza[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(pizza)):
cb[x]=i #조합 appending 중
dfs(x+1,i+1)
if __name__=='__main__' :
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
pizza=[]
house=[]
for i in range(n):
for j in range(n):
if a[i][j]==2:
pizza.append((i,j))
elif a[i][j]==1:
house.append((i,j))
cb=[0]*len(pizza) #조합을 저장해 둘 공간
dis=0
res=100000
dfs(0,0)
print(res)
조합 for i in range(s,len(sth)) 하고 다음 dfs부를 때
dfs(x+1,s+1)이 아니고
dfs(x+1,i+1) 이다
문제를 잘못 이해했었음.. 각 집마다 피자집의 거리 중 최소의 값들을 합친 것이 도시의 피자집거리 .. 문제를 잘 읽고 이해하자 바보야
=> 근데 이거 dfs로 푼게 아니고 그냥 야매로 푼 것..
==>그리고 문제도 잘못 이해해서 사실상 틀린 풀이, 그런데 답은 잘 나오네..ㅋㅋ
def dfs(x,y):
for i in hs:
mini=1000
#print('/')
for j in pz:
k=abs(i[0]-j[0]) + abs(i[1]-j[1])
#print(k,end='')
if k<mini:
mini=k
mm.append(mini)
if __name__=='__main__' :
pz=[]
hs=[]
mm=[]
n,m=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
for i in range(n) :
for j in range(n) :
if a[i][j]==1:
hs.append((i,j))
elif a[i][j]==2:
pz.append((i,j))
dfs(0,0)
print(sum(mm))