[CT] 병원 거리 최소화하기

1. 문제

• 도시 n * n

  • 각 칸 : 사람, 병원, 빈칸

  • 각 사람의 병원 거리 = 가장 가까운 병원까지 거리 : |x2 - x1| + |y2 - y1|

  • m개의 병원 남겨두고 나머지 폐업
    - m개의 병원 대한 각 사람들의 병원거리가의 총 합이 최소가 되도록

    ⇒ m개의 병원을 잘 골라 병원 거리의 총 합을 최소화하는 프로그램 작성

2. 풀이

• 백트래킹
• 주어진 병원들 중 m개를 골라서 병원거리 측정 ⇒ dfs함수, visited배열을 통해서 depth == m일 때만 병원 거리 계산
  
• 비슷한 문제 : 조삼모사

3. 코드

n, m = map(int, input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
 # 0:blank, 1:person, 2:hospital
people = []
hospital = []

for r in range(n):
    for c in range(n):
        if graph[r][c] == 1:
            people.append((r,c))
        elif graph[r][c] == 2:
            hospital.append((r,c))

len_h = len(hospital)
visited = [False] * len_h
result = float("INF")

def calc():
    res = 0
    for pr,pc in people:
        minh = 2 * n
        for i in range(len_h):
            if visited[i]:
                hr, hc = hospital[i][0], hospital[i][1]
                h = abs(pr - hr) + abs(pc - hc)
                minh = min(minh, h)
        res += minh
    return res
        

def dfs(depth, last_idx):
    global result, remain
    if depth == m:
        result = min(result, calc())
        return

    for i in range(last_idx + 1, len_h):
        visited[i] = True
        dfs(depth + 1, i)
        visited[i] = False

dfs(0, -1)

print(result)

+α