삼성 SW 역량 테스트 : 치킨 배달 (백준 15686번)

해당 문제는 백준에서 제공된 기출 문제입니다.

[문제 설명 및 파악]

15686번: 치킨 배달

먼저 문제의 요구가 무엇인지, 이러한 요구를 만족하기 위해 어떻게 접근해야 될지 알아보자. 일단 이 문제는 여러 치킨집 중 각 가정집들과의 거리가 최소가 될 수 있게 하는 M개의 치킨집을 선택하는 것이다. 그렇다면 이를 구하기 위해서는 어떻게 접근할까? 어렵게 생각이 들 수도 있지만, 이 문제는 모든 집과 모든 치킨집들이 고정되어 있기 때문에 단순하게 생각해서 각 집들의 모든 치킨집들 사이의 거리의 최솟값을 누적해서 반환하면 쉽게 풀 수 있는 문제이다. 그럼 이제 코드로 구현해 보자. (더 자세한 설명은 코드의 주석을 참조하자)

---

[문제 풀이]

from itertools import combinations
import sys


# 집과 치킨집의 위치를 기록하기 위한 함수
def find_loc(n, city_map):
    house = []
    chicken = []
    for i in range(n):
        for j in range(n):
            if city_map[i][j] == 1:
                house.append([i, j])
            elif city_map[i][j] == 2:
                chicken.append([i, j])
    return house, chicken


# 모든 집과 모든 치킨집들 사이의 거리 측정 함수
def cal_distance(house, chicken):
    distance = []  # 모든 집들에 대한 치킨집과의 거리를 저장 (한 row가 하나의 집을 기준으로 거리 측정한 결과)
    for h_i, h_j in house:
        line = []  # 각 집들에 대한 치킨집과의 거리를 저장
        for c_i, c_j in chicken:
            dis = abs(h_i - c_i) + abs(h_j - c_j)  # 거리 측정
            line.append(dis)
        distance.append(line)
    return distance


def get_min_city_chicken_distance(n, m, city_map):
    house, chicken = find_loc(n, city_map)  # 모든 집과 치킨집의 위치를 반환하여 저장
    # 최대 치킨집의 개수를 넘을 경우 치킨집을 제외하며 최소치킨거리를 측정
    if len(chicken) > m:
        if m == 1:  # 최대 치킨집의 수가 1이라면 (combinations를 통해선 1개만을 선택 못함)
            to_contain = [[i] for i in range(len(chicken))]  # 경우의 수 당 치킨집 1개씩 포함시켜줌
        else:  # 2개 이상이라면
            to_contain = list(
                combinations([i for i in range(len(chicken))], m))  # (중요!) combinations를 통해서 치킨집 중 m개만을 선택하는 모든 경우를 골라줌
            min_dis = sys.maxsize  # 거리의 최소값을 비교하기위해 초기값을 가장 큰값으로 설정
        for con_chi in to_contain:  # 위에서 설정한 경우의 수를 반복하며 탐색
            total_distance = 0
            new_chicken = [chicken[i] for i in range(len(chicken)) if i in con_chi] # 선택한 치킨집들의 위치를 새로 저장.
            distance = cal_distance(house, new_chicken) # 새로 설정한 m개의 치킨집들과 집들간의 거리를 측정해줌
            for house_dis in distance: # 측정된 거리 중 최소치킨거리를 선정
                total_distance += min(house_dis) # 최소치킨거리 누적
            min_dis = min(min_dis, total_distance) #각각의 경우의 수에서의 누적최소치킨거리 중 가장 최소값을 최소치킨거리로 설정
        return min_dis
    # 최대 치킨집의 개수를 넘지 않을 경우, 거리 계산 시 제외할 치킨집이 없으므로 최소값만 반영
    else:
        distance = cal_distance(house, chicken)  # 모든 집과 모든 치킨집 사의 거리를 측정 (row 하나 당 한 집과 모든 치킨집 사이의 거리)
        total_distance = 0  # 최소치킨거리
        for house_dis in distance:  # 각 집과 모든 치킨집 사이의 거리 중 최솟값을 선택
            total_distance += min(house_dis)  # 선택하여 최종 최소치킨거리에 누적
        return total_distance

이 문제를 풀면서 참고할만한 팁은 combination 툴을 이용하여 판단했다는 점이다. combination 툴은 반복 가능한 객체의 요소들 중 정해진 수만큼만 뽑아 반환해주는 툴이다. (ex. combination([1,2,3,4],2) 라고 하면 (1,2), (1,3), (1,4), ... ) 이를 이용해서 선택할 수 있는 m개의 치킨집의 경우를 모두 반환해 준다. 이렇게 반환된 치킨집을 통해서 거리를 측정하고 최솟값들을 비교해가면서 푼다면 큰 걸림돌은 없는 문제이다.

---

[마무리]

여러 기출들 중에서는 그래도 어렵지 않은 편에 속한다. 다만 코드를 구현하는 데에 있어서 짧지 않은 길이이기에 이를 얼마나 간결하고 정확히 푸느냐가 관건인 것 같다.