백준 15686 : 치킨 배달(파이썬)

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

15686번: 치킨 배달

오랜만에 가벼운 마음으로 풀 수 있는 문제를 만났다.
아직은 DFS 가 익숙하지 않아서.. 재귀함수로 접근하는 것이 어렵다.
그래서 치킨집의 개수 T와 폐업시키고 남길 치킨 집 수 M을 활용하여 조합 함수를 작성하였다.
itertools를 이용하면 더욱 쉽게 접근이 가능한 문제이지만, itertools를 활용하지 않고 조합 함수를 만들어서 썼다.
 
 1. 조합 함수
재귀함수 형태로 만들면 조합수 추출이 가능하다. 이해가 안되면 외우자. 순열은 언제 외우냐...

def gen_combination(arr, t) :
    result = []
    if t == 0 :
        return [[]]
    for i in range(len(arr)) :
        elem = arr[i]
        rest_arr = arr[i+1 : ]
        for C in gen_combination(rest_arr, t - 1) :
            result.append([elem] + C)
    return result

 2. 0은 빈 공간, 1은 집, 2는 치킨 집
2번째 줄부터 좌표정보를 받아올 때 반복문을 이용하여 좌표 정보를 추출하였다.
어차피 거리 계산하게 되므로, 좌표가 1부터 시작한다는 것은 딱히 신경안써도 된다.

for i in range(n) :
    info = list(map(int, input().split()))
    for j in range(len(info)) :
        if info[j] == 1 : h_list.append([i, j])
        if info[j] == 2 : c_list.append([i, j])

 3. 전체 코드
128144 KB 240 ms

n,m = map(int, input().split())
h_list, c_list = [], []
minValue = 1e9

for i in range(n) :
    info = list(map(int, input().split()))
    for j in range(len(info)) :
        if info[j] == 1 : h_list.append([i, j])
        if info[j] == 2 : c_list.append([i, j])

def gen_combination(arr, t) :
    result = []
    if t == 0 :
        return [[]]
    for i in range(len(arr)) :
        elem = arr[i]
        rest_arr = arr[i+1 : ]
        for C in gen_combination(rest_arr, t - 1) :
            result.append([elem] + C)
    return result

c_comb = gen_combination(c_list, m)

def solve() :
    global minValue
    for i in range(len(c_comb)) :
        result = 0
        for j in range(len(h_list)) :
            dist = []
            for k in range(m) :
                dist.append(abs(c_comb[i][k][0] - h_list[j][0]) + abs(c_comb[i][k][1] - h_list[j][1]))
            result += min(dist)
        minValue = min(result, minValue)

solve()
print(minValue)