[Baekjoon] 15686번 : 치킨 배달 (Python, 구현, 백트래킹)

[Baekjoon] 15686번 : 치킨 배달 (Python, 구현, 백트래킹)

 

목차

 

 

 

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

15686번: 치킨 배달

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 440ms / 코드 길이 704B

 

치킨 거리는 치킨집인 2와 집 1간의 Manhattan 거리에서 최소인 값을 구하는 것과 동일하다.

 

해당 문제를 풀 때는 m개의 치킨집에 대한 치킨 거리를 모두 구해 그 중 제일 작은 것을 골라야 한다.

즉, "치킨 거리가 작다는 것은 그만큼 각 집들과의 거리가 좁다는 것을 의미하고 그것은 수익이 늘어난다" 이런 시나리오인 듯 보인다.

 

여기서 유의해야하는 것은 그럼 m개를 어떻게 선정할 것인가이다.

여기서는 itertools.combinations를 통해 이를 해결했다.

그리고 그 값들을 토대로 각 집들과의 치킨거리를 구해 최소인 값을 출력했다. 

 

from itertools import combinations
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
l=[]
for i in range(n):
    l.append(list(map(int, input().split())))
o_loc = []
s_loc = []
for i in range(n):
    for j in range(n):
        if l[i][j] == 1:
            o_loc.append((i,j))
        elif l[i][j] == 2:
            s_loc.append((i,j))

t = combinations(s_loc, m)

def cal_sec(combi):
    sec_res = 0
    for one in o_loc:
        ox, oy = one
        mini = 1e9
        for sec in combi:
            sx, sy = sec
            mini = min(mini, abs(sx - ox) + abs(sy - oy))
        sec_res += mini
    return sec_res

mini = 1e9
for i in t:
    mini = min(mini, cal_sec(i))
print(mini)

 

 

 

방법 2 - 메모리 30840KB / 시간 656ms / 코드 길이 580B

 

방법 1을 조금 간소화한 버전이다.

 

from itertools import combinations
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
l=[list(map(int, input().split())) for _ in range(n)]
house = []
chick = []
for i in range(n):
    for j in range(n):
        if l[i][j] == 1:
            house.append((i,j))
        elif l[i][j] == 2:
            chick.append((i,j))

res = 1e9
for ch in combinations(chick, m):
    tmp = 0
    for hx, hy in house:
        mini = 1e9
        for cx, cy in ch:
            mini = min(mini, abs(hx - cx) + abs(hy - cy))
        tmp += mini
    res = min(res, tmp)
print(res)

  

 

방법 3 - 메모리 30840KB / 시간 476ms / 코드 길이 946B

 

본 문제는 백트래킹 문제이다.

위에서는 쉽게 내장 함수를 통해 처리했지만 만약 내장함수가 없다면 다음과 같은 코드를 통해 처리해야한다.

 

치킨 거리를 계산하는 함수

백트래킹의 조건을 위한 함수

 

백트래킹의 경우 치킨집의 추가를 위해 새로운 list인 t_ch를 사용. 그리고 해당 치킨집의 방문처리를 위한 visit list를 사용한다.

 

def cal():
    tmp = 0
    for hx, hy in house: # 1에 위치하는 모든 house를 하나씩 뽑아 치킨 거리를 구함
        dist = 1e9
        for e, (cx, cy) in t_ch: # 2에 위치한 치킨집과 특정 house와의 치킨 거리 구함.
            dist = min(dist, abs(hx - cx) + abs(hy - cy))
        tmp += dist
    res.append(tmp)

def select_chicken(cnt):
    # 백트래킹의 조건으로 m과 숫자가 일치할 때 치킨 거리를 구해 res 리스트에 저장
    if cnt == m:
        cal()
        return

    for e, (cx, cy) in enumerate(chick):
        if visit[cx][cy] == 0: # 특정 치킨 집을 방문했는지 처리함.
            if t_ch: # 시간 단축과 오름차순의 조합이 가능하도록 하기 위해 배치
                if e < t_ch[-1][0]:
                    continue

            visit[cx][cy] = 1 # 특정 치킨집 방문 처리
            t_ch.append((e, (cx,cy)))
            select_chicken(cnt + 1) 
            visit[cx][cy] = 0 # 특정 치킨집 방문 철회
            t_ch.pop() 

n, m = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
house = []
chick = []
visit = [[0]*(n) for _ in range(n)]
t_ch = []
res = []
for i in range(n):
    for j in range(n):
        if l[i][j] == 1:
            house.append((i,j))
        elif l[i][j] == 2:
            chick.append((i,j))

select_chicken(0)
print(min(res))