🐨BOJ#15686]치킨 배달

from itertools import combinations


def read_input():
    data = open(0).read().split()
    N = int(data[0])
    M = int(data[1])
    city = [list(map(int, data[i*N+2:(i+1)*N+2])) for i in range(N)]
    return N, M, city

def find_locations(city, N):
    chicken, house = [], []
    for r in range(N):
        for c in range(N):
            if city[r][c] == 1:
                house.append((r, c))
            elif city[r][c] == 2:
                chicken.append((r, c))
    return chicken, house

def calculate_city_chicken_distance(chicken, house, M):
    min_distance = float('inf')
    for chickens in combinations(chicken, M):
        city_distance = 0
        for hr, hc in house:
            min_dist = float('inf')
            for cr, cc in chickens:
                dist = abs(hr - cr) + abs(hc - cc)
                if dist < min_dist:
                    min_dist = dist
            city_distance += min_dist
            if city_distance >= min_distance:
                break
        if city_distance < min_distance:
            min_distance = city_distance
    return min_distance

N, M, city = read_input()
chicken, house = find_locations(city, N)
result = calculate_city_chicken_distance(chicken, house, M)
print(result)

코드 설명

1. read_input 함수:
   • 입력을 처리하여 N, M 및 도시의 맵을 반환합니다.
   • open(0).read()를 사용하여 한 번에 전체 입력을 읽습니다.
2. find_locations 함수:
   • 도시 맵에서 치킨집과 집의 위치를 추출합니다.
3. calculate_city_chicken_distance 함수:
   • 모든 가능한 치킨집 조합을 생성하고, 각 조합에 대해 도시의 치킨 거리를 계산합니다.
   • 치킨 거리는 각 집에서 선택된 치킨집 중 가장 가까운 거리의 합입니다.

 

맨하탄 거리 관련 동심원 탐색 아이디어.

0zx0 님의 소스코드. 제일 빨랐다.

N, M = map(int, input().split())
hs, cs = [], []
for r in range(N):
    for c, n in enumerate(map(int, input().split())):
        if n == 1:
            hs.append((r, c))
        elif n == 2:
            cs.append((r, c))
C = len(cs)
answer = (2*N)**2
v = [0 for _ in range(C)]

def ham_distance(c, h):
    return abs(c[0]-h[0]) + abs(c[1]-h[1])

# row -> 특정 h에 대한 c 거리들.
ds = [sorted([(i, ham_distance(h, c)) for i, c in enumerate(cs)], key = lambda x : x[1]) for h in hs]

# 바꾸고 싶은 것만 global로 전달.
# 정렬을 미리 해서 for loop 내에서 정렬을 반복하지 않도록 한다.
def dfs(depth, cur_loc):
    global answer, v
    if depth == M:
        tmp = 0
        for hds in ds:
            for i, d in hds:
                if v[i]:
                    tmp += d
                    break
        answer = min(tmp, answer)
    else:
        for i in range(cur_loc, C-M+depth+1):
            v[i] = 1
            dfs(depth+1, i+1)
            v[i] = 0

def solve():
    dfs(0, 0)
    return

solve()
print(answer)