2018_상_P_2_L11

병원 거리 최소화하기

Backtracking

평균 : 92'

---

피곤 이슈 & 내일 대회 이슈로 포기

sol : -

• 수행 시간: -
• 메모리: -

import sys
import collections

MAX_HOSPITAL = 13
INT_MAX = sys.maxsize

# 변수 선언 및 입력
n, m = tuple(map(int, input().split()))
given_map = [
    list(map(int, input().split()))
    for _ in range(n)
]
people = [
    (i, j)
    for i in range(n)
    for j in range(n)
    if given_map[i][j] == 1
]
hospitals = [
    (i, j)
    for i in range(n)
    for j in range(n)
    if given_map[i][j] == 2
]
visited = [
    False for _ in range(MAX_HOSPITAL)
]
checked = list()
step = list()

min_distance = INT_MAX


# bfs시 나아가려는 위치가 격자 내에 아직 방문하지 않은 지점인지를 판단합니다.
def can_go(x, y):
    return 0 <= x and x < n and 0 <= y and y < n and not checked[x][y]


# m개의 병원이 선택됐을 때 각 사람의 병원 거리에 대한 합을 반환해줍니다.
def get_curr_min_distance():
    global checked, step
    
    # bfs에 필요한 값들을 전부 초기화합니다.
    q = collections.deque()
    
    checked = [
        [False for _ in range(n)]
        for _ in range(n)
    ]
    step = [
        [0 for _ in range(n)]
        for _ in range(n)
    ]
    
    for i, (hx, hy) in enumerate(hospitals):
        if visited[i]:
            checked[hx][hy] = True
            step[hx][hy] = 0
            q.append((hx, hy))
    
    # bfs를 수행합니다.
    dxs, dys = [1, -1, 0, 0], [0, 0, 1, -1]
    while q:
        curr_x, curr_y = q.popleft()
        
        for (dx, dy) in zip(dxs, dys):
            nx, ny = curr_x + dx, curr_y + dy
            if can_go(nx, ny):
                checked[nx][ny] = True
                step[nx][ny] = step[curr_x][curr_y] + 1
                q.append((nx, ny))
    
    # 각 사람에 대하여 가장 가까운 병원의 거리를 구합니다.
    return sum([
        step[px][py]
        for (px, py) in people
    ])


def search_min_distance(cnt, last_idx):
    global min_distance
    
    # m개의 병원이 선택되었을 경우 병권 거리의 총합을 구해줍니다.
    if cnt == m:
        min_distance = min(min_distance, get_curr_min_distance())
        return
    
    # 뽑을 수 있는 병원의 후보들을 탐색합니다.
    for i in range(last_idx + 1, len(hospitals)):
        visited[i] = True
        search_min_distance(cnt  + 1, i)
        visited[i] = False


search_min_distance(0, -1)
print(min_distance)