[python] 백준 15686 - 치킨 배달

출처 : 백준, https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

 

먼저, 생각해야 할 부분

 

1. 1개를 골랐을 때 최대 m개라면, m개를 골랐을 때도 같은 값이 나온다.

     m개가 최댓값이라면 m개를 골랐을 때 최댓값이 나온다.

 

     최대 m개를 골라야하지만, 어짜피 m개보다 작게 고른 경우의 수가 m개를 뽑았을 때도 포함되어 있으므로,

     1~m개를 모두 계산하는게 아니라 m개를 고른 경우에 대해서만 계산하면 된다.

 

---

 

풀이

 

def combination(list, count):
    if count == 1:
        return [[i] for i in list]

    combi_list = []

    for i in range(len(list)):
        fix_element = list[i]

        for combi in combination(list[i + 1:], count - 1):
            combi_list.append([fix_element] + combi)

    return combi_list

def calcManhattanDis(p1, p2):
    ar, ac = p1
    br, bc = p2

    return abs(ar - br) + abs(ac - bc)

def solution(n, m, city_map):
    BLANK = 0
    HOME = 1
    CHICKEN = 2

    homeList = []
    chickenList = []

    # N^2
    for i in range(n):
        for j in range(n):
        # 집과 치킨집을 모두 찾아 좌표화 시킨다.
            if city_map[i][j] == HOME:
                homeList.append((i, j))
            elif city_map[i][j] == CHICKEN:
                chickenList.append((i, j))

    # 치킨집의 조합을 만든다.
    combi_list = combination(chickenList, m)

    # 최소 거리를 구한다.
    # 하나의 조합을 가져온다.
    # 모든 집에 대해서 각 조합의 집 중 가장 거리가 작은 것을 누적한다. => 해당 조합의 치킨 거리
    # min_dis와 비교해서 업데이트한다.
    min_dis = float("inf")

    for combi in combi_list:
        combi_min_dis = 0

        for home in homeList:
            # 각 집별로 가장 가까운 치킨집과의 거리를 구해 누적
            combi_min_dis += min([calcManhattanDis(home, chicken) for chicken in combi])

        if combi_min_dis < min_dis:
            min_dis = combi_min_dis

    return min_dis

n, m = map(int, input().split())
city_map = [list(map(int, input().split())) for _ in range(n)]

print(solution(n, m, city_map))

 

---

알게 된 점

 

python의 무한대(infinity)

 

import math

inf = math.inf
inf = float('inf')

 

고찰

 

이전에 풀었던 풀이는 아래와 같은 코드가 더 들어가 있었다.

 

# 각 집에서 모든 치킨집까지의 거리를 모두 구한다.
    for cr, cc in chickenList:
        for key in homeList.keys():
            hr, hc = makeKeyToPoint(key)

            homeList[key][makePointToKey(cr, cc)] = calcManhattanDis((cr, cc), (hr, hc))

 

각 집 별로 모든 치킨집에 대해 맨하탄 거리를 구해놓고 이를 조회하는 것이 빠를 것이라 생각해서 작성한 코드였는데,

어짜피 맨하탄 거리는 계산하는 것은 O(1)이어서

나중에 어짜피 조합별 * 집별로 for문을 돌아야할 때 계산해도 소요 시간이 크지 않고,

오히려 위의 코드처럼 별도로 다 계산해두는 것이 O(N^2)으로 더 많은 시간을 걸리게 만들었다.

 

따라서, 단순 계산으로 구할 수 있는 것들은 반복문을 돌면서 그때그때 구하는 것이

미리 구해서 조회하는 것보다 훨씬 빠르다는 것을 알아두자.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들

 

Reference

조합의 코드화