[백준/파이썬]15686 치킨 배달

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

15686번: 치킨 배달

 

문제

백준15686번 치킨 배달

백트래킹 문제다.

 

도시의 집과 치킨집의 위치가 주어 졌을때, 치킨집을 m개만 남겼을 경우 도시의 치킨 거리(집과 치킨집 거리가 최소가 되는 합)가 최소가 되는 값을 찾는 문제다.

 

나는 이 문제를 풀기 위해 우선 치킨집을 m개만 남기는 경우의 수를 찾았다.

 

각 치킨집의 좌표(x,y)를 하나의 리스트에 저장하고, 이걸 콤비네이션 연산 하면 된다.

 

def make_combination(select_count, select_xy, visit, start) :
    global combination
    if select_count == m :
        combination.append(select_xy)
    
    for i in range(start, len(chicken_xy)) :
        if visit[i] :
            continue
        visit[i] = True
        make_combination(select_count+1, select_xy+[chicken_xy[i]], visit, i+1)
        visit[i] = False

map_ = [list(map(int, input().split())) for _ in range(n)] # 도시
chicken_xy = []
home_xy = []
for i in range(n) :
    for j in range(n) :
        if map_[i][j] == 2 :
            chicken_xy.append((i,j))
        elif map_[i][j] == 1:
            home_xy.append((i,j))

 

치킨집은 chicken_xy에 저장하고, 집은 home_xy에 저장한다.

 

그 후 make_combination함수를 이용해 DFS로 조합을 구한다.

 

예제 입력2번을 예시로 

5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

 

를 입력했을 경우

 

치킨집 좌표들 :

[(0, 1), (3, 0), (4, 0), (4, 1), (4, 4)]

 

치킨집들 중 m개(2개)를 고르는 경우의 수 :

[[(0, 1), (3, 0)], 

 [(0, 1), (4, 0)],

 [(0, 1), (4, 1)],

 [(0, 1), (4, 4)],

 [(3, 0), (4, 0)],

 [(3, 0), (4, 1)],

 [(3, 0), (4, 4)],

 [(4, 0), (4, 1)],

 [(4, 0), (4, 4)],

 [(4, 1), (4, 4)]]

 

이렇게 나오게 된다. (5C3 => 6개의 경우의 수)

 

각각의 경우에 집과 치킨집의 거리가 최소가 되는 합을 구하고, 이 합이 최소가 되는 값이 정답이 된다.

 

정답

import sys

def make_combination(select_count, select_xy, visit, start) :
    global combination
    if select_count == m :
        combination.append(select_xy)
    
    for i in range(start, len(chicken_xy)) :
        if visit[i] :
            continue
        visit[i] = True
        make_combination(select_count+1, select_xy+[chicken_xy[i]], visit, i+1)
        visit[i] = False

input = sys.stdin.readline

n, m = map(int, input().split())

map_ = [list(map(int, input().split())) for _ in range(n)]

chicken_xy = []
home_xy = []
for i in range(n) :
    for j in range(n) :
        if map_[i][j] == 2 :
            chicken_xy.append((i,j))
        elif map_[i][j] == 1:
            home_xy.append((i,j))

combination = []
visit = [False for _ in range(len(chicken_xy))]

make_combination(0, [], visit, 0)

ans = 9999999
for chicken_ in combination :
    sum_ = 0
    for home_ in home_xy :
        min_ = 99999
        for tuple_ in chicken_ :
            minus = abs(tuple_[0] - home_[0]) + abs(tuple_[1] - home_[1])
            if min_ > minus :
                min_ = minus
        sum_ += min_
    if sum_ < ans :
        ans = sum_
print(ans)