[삼성SW역량][Python/BOJ] 백준 15686 치킨 배달(DFS)

 

 

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

 

 

 

 

 

조합을 이용해서 치킨집들의 조합을 구한다.

이 치킨집들과 집들의 각각 치킨거리를 구해 가장 작은 값을 구하면 된다. 

 

 

 

 

---

 

 

 

 

코드 : 

<DFS 이용_조합을 직접 만듦>

n,m = map(int,input().split())
mp =  [list(map(int,input().split())) for i in range (n)]

hs = []
ch = []
cb = [0]*m # 조합 # 선택할 치킨집의 인덱스를 담은 배열 (combination)
res = int(1e9)


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 = int(1e9)
            for x in cb : #   치킨집 좌표 
                x2 = ch[x][0]
                y2 = ch[x][1]
                dis = min(dis, abs(x2-x1)+abs(y1-y2))
            sum += dis 
        if sum <res : res = sum
        
    else :
        for i in range(s,len(ch)) :
            cb[L] = i
            dfs(L+1,i+1) 
            
for i in range(n) :
    for j in range(n) :
        if mp[i][j] == 1 : #  집 발견 
            hs.append((i,j))
        elif mp[i][j]==2 : # 치킨집 발결 
            ch.append((i,j))
dfs(0,0)
print(res)

 

 

 

이후 풀이 : <combinations 이용>

def bfs(sel) :
    res = 0 # 도시의 치킨거리
    for pos in hs :
        tmp = int(1e9) # 해당 집의 치킨거리 
        for pos2 in sel :
            tmp = min(tmp,abs(pos[0]-pos2[0])+abs(pos[1]-pos2[1]))
        res+= tmp
    return res

if __name__=="__main__" :
    n,m = map(int,input().split())
    mp = [list(map(int,input().split())) for i in range(n)]
    hs = []
    ch = []

    for i in range(n) :
        for j in range(n) :
            if mp[i][j] == 1 : # 집일 경우 
                hs.append([i,j])
            elif mp[i][j] == 2 : # 치킨집일 경우 
                ch.append([i,j])
    ans = int(1e9)
    for select in c(ch,m) :
        ans = min(ans, bfs(select))
    print(ans)

 

 

 

코드는 인프런 - 김태원

피자배달거리를 참고하였다. 

 

 

---

 

 

 

 

복습을 하면서 만든 풀이 : 

def dfs(idx,cnt) :
    global ans 
    if idx == m :
        ans = min(ans,city())
        return 
    else :
        for added in range(cnt+1, len(chick)) :
            x,y = chick[added]
            mp[x][y] = 3 
            dfs(idx+1, added)
            mp[x][y] = 2 

def city() :
    city_dist = 0
    for x,y in house :
        home_dist = int(1e9)
        for i in range(n) :
            for j in range(n) :
                if mp[i][j] == 3 :
                    home_dist = min(abs(i-x) + abs(j-y), home_dist)
        city_dist += home_dist
    return city_dist
       
if __name__=="__main__" :
    n,m = map(int,input().split())
    mp = [list(map(int,input().split())) for _ in range(n)]
    house, chick = [],[]

    for i in range(n) :
        for j in range(n) :
            if mp[i][j] ==1 : house.append([i,j])
            elif mp[i][j] ==2 : chick.append([i,j])
    ans = int(1e9)
    dfs(0,-1)
    print(ans)

 

 

 

 

 

풀리기는 풀리는데 시간이 정말 많이든다. 

 

치킨집들을 돌면서 m개를 선택하여 3으로 만들고 

city()에서 도시의 치킨거리를 구한다. 

 

 

 

 

그런데 이렇게 combinations이용해서 뽑는게 확실히 빠르다. 

c(chick, m) 은 첫번째 인수로 받은 chick 리스트에서 m개를 뽑아 리스트를 만든다. 

그 리스트를 k 로 돌면서 street ()에 인수로 준다. 

인수로 넘어간 k는 선택된 치킨집의 위치를 가진다. 

 

from itertools import combinations as c
def street(select) :
    city_dist = 0
    for h in house : 
        ch = int(1e9)
        for s in select :
            ch = min(ch, abs(s[0]-h[0]) + abs(s[1] - h[1]))
        city_dist += ch 
    return city_dist
       
if __name__=="__main__" :
    n,m = map(int,input().split())
    mp = [list(map(int,input().split())) for _ in range(n)]
    house, chick = [],[]

    for i in range(n) :
        for j in range(n) :
            if mp[i][j] ==1 : house.append([i,j])
            elif mp[i][j] ==2 : chick.append([i,j])
    ans = int(1e9)
    
    # 치킨집 중에서 m개를 뽑는다. 
    for k in c(chick,m) :
        ans = min(ans,street(k))
        
    print(ans)

 

 

 

 

 

 

복습 : 

✅ 20220712

✅ 20220719

🐾 20220918