[Python 3] BOJ 15686 치킨 배달

오늘의 문제는 치킨 배달이라는 문제이다. (골드 5)

DFS를 통해서 해결방법을 구현하였다.

문제 BOJ 15686

해결 코드이다.

import sys
input=sys.stdin.readline
def dist(a,b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])

n,m=map(int,input().split())
data=[]
for i in range(n):
    data.append(list(map(int,input().split())))
chicken=[]
house=[]
for i in range(n):
    for j in range(n):
        if data[i][j]==1:
            house.append([i,j])
        elif data[i][j]==2:
            chicken.append([i,j])
dists=[]
for i in range(len(house)):
    tempL=list()
    for j in range(len(chicken)):
        tempL.append(dist(house[i],chicken[j]))
    dists.append(tempL)

score=1e10
visited=[False]*len(dists[0])
def dfs(temp,latest):
    global score
    if len(temp)==m:
        
        setscore=0
        for n1 in range(len(dists)):
            comp=1e10
            for n2 in range(len(dists[0])):
                if n2 in temp:
                    comp=min(comp,dists[n1][n2])
            setscore+=comp
        score=min(setscore,score)
        return
    for i in range(latest,len(dists[0])):

        if not visited[i]:
            visited[i]=True
            temp.append(i)
            latest+=1
            dfs(temp,latest)
            visited[i]=False
            temp.pop()
        
dfs([],0)
print(score)

하나하나 보자면, dist()라는 함수는 두 좌표 사이의 거리를 구하는 함수이다. 

수학 용어 중에 '택시 거리'라 하여, 두 좌표의 거리를 x좌표끼리, y좌표끼리의 차를 합하여 구하는 거리이다.

우선 모든 좌표들을 input을 받고, 일반 집과 치킨 집의 좌표를 리스트에 넣는다.

이후 집에서 모든 치킨 집 까지의 거리를 구하고, dists라는 리스트에 포함시켰다.

여기서  살려야 할 (폐업하지 않아야 할) 치킨집들을 combination, 조합을 통해 구현하여 최저거리를 구했다.

 

처음에는 어려웠지만, 막상 풀면 기본적인 알고리즘을 통해 해결할 수 있었다.