문제

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

나의 코드

"""

"""

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

n, m = map(int, input().split())
pan = [ [0] + list(map(int, input().split())) for _ in range(n) ]
pan.insert(0, [0] * (n+1))
chicken = []
home = []

for i in range(1, n+1): # 집의 좌표와 치킨집의 좌표를 기록하고 치킨집은 0으로 초기화 한다.(백트래킹을 위해)
    for j in range(1, n+1):
        if pan[i][j] == 1:
            home.append((i, j))
        if pan[i][j] == 2:
            chicken.append((i, j))
            pan[i][j] = 0

def chicken_search(): # 모든 집의 치킨거리를 구하는 함수
    global answer

    tmp = [] # 백트래킹으로 새로 배치된 치킨집의 좌표를 받는 변수
    for i in range(1, n+1):
        for j in range(1, n+1):
            if pan[i][j] == 2: # 백트래킹으로 새로 배치된 치킨집의 좌표를 기록한다.
                tmp.append((i, j))

    all_distance = 0 # 모든 집의 치킨거리를 담는 변수
    for i, j in home:
        distance = 1e9 # 한 집의 치킨거리를 담는 변수
        for x, y in tmp:
            distance = min(distance, abs(i-x)+abs(j-y)) # 한 집의 치킨거리의 최소값을 담는다.

        all_distance += distance

    answer = min(answer, all_distance) # 모든 경우의 수(백트래킹)에 대해 모든 집의 치킨거리가 최소인 경우를 구한다.

def chicken_arrange(depth, idx): # 백트래킹을 위해 치킨집을 배치하는 함수

    if depth == m: # 최대 m개 만큼 치킨집을 배치하면 도시의 치킨거리를 구한다.
        chicken_search()
        return

    for i in range(idx, len(chicken)): # 백트래킹을 이용해 m개 만큼 치킨집을 배치한다.
        x, y = chicken[i]
        pan[x][y] = 2
        chicken_arrange(depth+1, i+1)
        pan[x][y] = 0

answer = 1e9
chicken_arrange(0, 0)
print(answer)
    

설명

삼성 기출인 사다리 조작과 비슷한 형태의 백트래킹을 이용한다.

최대 m개의 치킨 집을 백트래킹으로 배치한 다음 m개 만큼 치킨 집이 배치된다면 모든 집의 치킨 거리를 구하는 함수를 통해 치킨 거리를 최소값으로 업데이트 해주면 된다.

참고 자료