[백준 15686번] 치킨 배달

델리만쥬 디퓨저·2024년 10월 23일

알고리즘

목록 보기

14/15

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

실패 코드

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]

chicken = []


def calc_distance(x, y):
    min = 999
    min_chicken = 0
    for c in chicken:
        dist = abs(x - c[0]) + abs(y - c[1])
        if dist < min:
            min = dist
            min_chicken = c
    min_chicken[2] += 1

    return min


for i in range(N):
    for j in range(N):
        if arr[i][j] == 2:
            chicken.append([i, j, 0])

res = 0
for i in range(N):
    for j in range(N):
        if arr[i][j] == 1:
            calc_distance(i, j);

chicken = sorted(chicken, key=lambda x: x[2])
while len(chicken) > M:
    if chicken[0][2] == chicken[-1][2] and len(chicken) > M + 1:
        chicken.pop(0)
        chicken.pop(-1)
    else:
        chicken.pop(0)

for i in range(N):
    for j in range(N):
        if arr[i][j] == 1:
            res += calc_distance(i, j);

print(res)

기존 구현하려던 흐름

치킨집과 집의 좌표를 추출한다
2중 for문을 통해 모든 좌표에 대해서 거리를 계산하는 함수를 실행한다
함수는 치킨집 중 가장 적은 치킨거리를 가진 값을 반환하고, 해당 치킨집의 접근 횟수를 증가시킨다.
이 과정을 통해 접근 횟수가 가장 많은 치킨집을 M개만큼 남긴다
남은 치킨집으로 다시 계산을 해서 결과를 출력한다

문제점

..........

모든 치킨집의 접근 횟수가 동일하다면?
- 이 경우 좌표의 중간 값으로 계산하는 방식으로 구현해 해결하려고 하였음
- 4개의 테스트 코드에 대한 정답을 출력하는 데는 성공했으나, 이는 근본적인 해결책이 되지 못함

(정답 슬쩍)

아 딱 알았다!

itertools의 combinations 함수를 사용
- M개의 치킨집의 조합을 모두 생성한다
- 해당 조합에 대해서 집들에 대한 치킨 거리를 계산해 합을 구한다
- 만약 최소 값과 비교해서 더 작은 값이라면 갱신한다

정답 코드

from itertools import combinations

N, M = map(int, input().split())
city = [list(map(int, input().split())) for _ in range(N)]

houses = []
chickens = []

for i in range(N):
    for j in range(N):
        if city[i][j] == 1:
            houses.append([i, j])
        elif city[i][j] == 2:
            chickens.append([i, j])

min_city_chicken_distance = float('inf')

for chicken_comb in combinations(chickens, M):
    city_chicken_distance = 0
    for hx, hy in houses:
        chicken_distance = min(abs(hx-cx)+abs(hy-cy) for cx, cy in chicken_comb)
        city_chicken_distance += chicken_distance

    if city_chicken_distance < min_city_chicken_distance:
        min_city_chicken_distance = city_chicken_distance

print(min_city_chicken_distance)