[BaekJoon] 15686번 : 치킨 배달 (Python)

코딩 1일 1문제! 오늘의 문제는 백준의 치킨 배달 입니다.

15686번: 치킨 배달

Solution

from itertools import combinations

def find_home_chicken(city_map):
    home, chicken = [], []
    for i, row in enumerate(city_map):
        for j, col in enumerate(row):
            if row[j] == 1:
                home.append((i, j))
            elif row[j] == 2:
                chicken.append((i, j))
                
    return home, chicken


def get_home_chicken_distance(home_point, chicken_point):
    return abs(home_point[0] - chicken_point[0]) + abs(home_point[1] - chicken_point[1])
            

def chicken_delivery(max_chicken, city_map):
    home, chicken = find_home_chicken(city_map=city_map)
    
    number_of_cases = list(combinations(chicken, max_chicken))
    
    case_distance = [0 for _ in range(len(number_of_cases))]
    
    for i in range(len(home)):
        for j in range(len(number_of_cases)):
            dist = 100
            for case in number_of_cases[j]:
                dist = min(dist, get_home_chicken_distance(home[i], case))
            case_distance[j] += dist
    return min(case_distance)

if __name__ == "__main__":
    city_map = []
    N, M = map(int, input().split())
    for i in range(N):
        city = list(map(int, input().split()))
        city_map.append(city)
        
    print(chicken_delivery(max_chicken=M, city_map=city_map))

Solution 풀이

먼저 입력 받은 2차원 배열에서 집과 치킨집의 위치를 찾아 따로 home과 chicken 리스트에 담아둡니다.

그 다음 내가 남겨둬야하는 치킨집의 개수 정보 N과 Python itertools의 combinations를 활용하여

N개씩 묶인 치킨집 조합을 구하여 number_of_cases에 넣어 줍니다. ( 내가 남겨두는 치킨집의 모든 경우의 수 )

각 케이스마다의 치킨거리를 저장할 리스트를 list comprehension을 활용하여 만들어줍니다.

그럼 이제 각 케이스와 아까 찾아둔 집 위치 정보를 활용하여 각 치킨집과 집과의 거리를 구해

치킨 거리를 구합니다.

거리를 구하는 함수는 get_home_chicken_distance로 만들어주었습니다.

각 케이스마다 치킨거리가 구해지면 그 중 가장 작은 값을 최종적으로 출력하도록 하면 끝입니다.

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07