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

풀이 및 해설(주석)

import sys

def solve(m, index):
    global rst
    if m == M:
        cnt = 0
        for home in homes:
            r, c = home[0], home[1]
            tmp = 2*N+1
            for chick in ans:
                er, ec = chick[0], chick[1]
                if (abs(er-r) + abs(ec-c)) < tmp:
                    tmp = abs(er-r) + abs(ec-c)
            cnt += tmp
            if tmp > rst:
                return
        rst = min(rst, cnt)
        return

    for i in range(index, chicks_len):
        ans.append(chicks[i])
        solve(m+1, i+1)
        ans.pop()


N, M = map(int, sys.stdin.readline().strip().split())

city = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]

# 1이면 homes에, 2면 chicks에 더해준다.
homes = []
chicks = []
for i in range(N):
    for j in range(N):
        if city[i][j] == 1:
            homes.append((i, j))
        elif city[i][j] == 2:
            chicks.append((i, j))

# dfs 탐색을 위해 길이를 구해준다.
chicks_len = len(chicks)

# ans는 임시로 사용할 치킨집의 위치를 저장하는 배열
ans = []
rst = 9e9

# 완전탐색을 위해 첫 인덱스 부터 쭉 돌려준다.
for i in range(chicks_len-M+1):
    solve(0, i)

print(rst)

 

---

후기

• 진짜 오랜만에 푼 골드 문제임(알고리즘을 사실 오랜만에 품)
• 전형적인 백트래킹 문제였으나, 초반에 고민을 좀 했다..
• 치킨집을 고르는 로직이 중점이었다. 
• 지금 생각해보니 저거 itertools사용해서 풀어도 될 것 같다?
• 알고도 조금씩 해야되는데.. 재미가 없어..