[백준 15686] 치킨 배달

문제 출처 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

치킨을 배달할 수 있는 치킨 거리가 가장 짧아지는 경우를 구하는 문제 입니다. 여기서 거리를 구하는 방식은 맨하탄 거리(Manhattan Distance)를 구하는 공식 입니다. 좌표간의 거리를 구하는 방식 중 하나로 간단한 계산으로 거리를 구할 수 있습니다.

알고리즘

지도의 크기 N의 최대는 50이고 치킨 집의 개수의 최대는 13입니다. 이정도의 크기라면 브루트 포스로 충분히 해결 가능한 크기라는 것을 알 수 있습니다.

치킨집의 개수를 M개의 조합으로 만든 다음, 치킨 거리를 계산하여 최소가 나오는 조합을 찾아 치킨 거리를 출력하면 되는 문제 입니다. 치킨 집의 개수가 작기 때문에 할 수 있는 방법 입니다.

코드 작성

그럼 문제를 풀어보도록 하겠습니다.

입력 받기

mii = lambda : map(int, input().split())

N, M = mii()

house = []
chicken = []
for i in range(N):
    row = list(mii())
    for j in range(N):
        if row[j] == 1:
            house.append((i, j))
        elif row[j] == 2:
            chicken.append((i, j))

지도의 크기 N과 치킨 집의 최대값 M을 입력 받습니다. 다음으로 지도를 입력 받아 그 값이 1이면 집 리스트인 house에 넣고, 2이면 치킨 집 리스트인 chicken에 넣습니다. 이 때 좌표값이 x, y 순이 아니라 y, x 순으로 입력 받았습니다. 자신이 기억하기 편한 방법으로 입력을 넣어줍니다.

조합 구하기

from itertools import combinations

ans = 1e9
for comb_chicken in combinations(chicken, M):
    ans = min(ans, get_dist(comb_chicken))

print(ans)

조합을 만들기 위해서 itertools의 combinations를 import 해줍니다. 최소값을 구하는 것이기 때문에 초기값을 최대의 값으로 해줍니다. 그리고 조합을 돌면서 거리를 구해줍니다. 그 거리의 최소값을 정답으로 합니다. 조합에 대해 잘 모른다면 여기를 확인해 보시기 바랍니다.

치킨 거리 구하기

조합에서 사용하는 거리 구하는 함수 get_dist를 작성해 보겠습니다.

def get_dist(cc):
    ans = 0
    for hy, hx in house:
        temp = 1e9
        for cy, cx in cc:
            temp = min(temp, abs(cy - hy) + abs(cx - hx))
        ans += temp
    return ans

모든 집에서부터 치킨 집까지의 거리를 구해줍니다. cc에는 치킨집의 조합이 들어 있기 때문에 거리의 최소값을 업데이트 하면 해당 조합의 최소 치킨 거리를 구할 수 있습니다. 중복되는 계산이 많아보이기는 하지만 N의 크기가 작기 때문에 이렇게 해도 충분히 답을 구할 수 있습니다.

전체 코드

전체 코드를 살펴 보겠습니다.

from itertools import combinations

mii = lambda : map(int, input().split())

N, M = mii()

house = []
chicken = []
for i in range(N):
    row = list(mii())
    for j in range(N):
        if row[j] == 1:
            house.append((i, j))
        elif row[j] == 2:
            chicken.append((i, j))

def get_dist(cc):
    ans = 0
    for hy, hx in house:
        temp = 1e9
        for cy, cx in cc:
            temp = min(temp, abs(cy - hy) + abs(cx - hx))
        ans += temp
    return ans

ans = 1e9
for comb_chicken in combinations(chicken, M):
    ans = min(ans, get_dist(comb_chicken))

print(ans)

2023년 정보올림피아드 초등부 문제이자, 백준 28215번 대피소라는 문제와 굉장히 유사합니다. 아직 풀어보지 않았다면 대피소도 꼭 풀어 보시기 바랍니다.