071 | 피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용)

71. 피자 배달 거리(삼성 SW역량평가 기출문제 : 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

<내 풀이>

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))
    

<풀이>

• 위에 내가 생각한 개념에 조합을 추가하면 됨,,
  (아..조합도 아까 고려했었는데 ㅠㅠ 아쉽)

• 이중 for문 돌릴 때 집을 위에 두고 그다음에 피잣집들을 계산해줘야 함

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) 이다

• 문제를 잘못 이해했었음.. 각 집마다 피자집의 거리 중 최소의 값들을 합친 것이 도시의 피자집거리 .. 문제를 잘 읽고 이해하자 바보야

<배운 점>

<2차 내 풀이>

=> 근데 이거 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))