10_삼성역량테스트3

치킨게임 문제였다. 마지막 문제치고는 다른 문제들에 비해 엄청 간단한 문제였는데, 크게 어렵지 않았다.

 

 

 

 

import itertools, sys

n = 5
m = 3

city_map = [
    [0, 0, 1, 0, 0],
    [0, 0, 2, 0, 1],
    [0, 1, 2, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 0, 2],
]


def get_min_city_chicken_distance(n, m, city_map):
    chicken_location_list=[]
    home_location_list=[]
    for i in range(n):
        for j in range(n):
            if city_map[i][j] == 1:
                home_location_list.append([i,j])
            elif city_map[i][j] == 2:
                chicken_location_list.append([i,j])


    chicken_location_m_combinations = list(itertools.combinations(chicken_location_list,m))
    min_distance_of_m_combinations = sys.maxsize

    for chicken_location_m_combination in chicken_location_m_combinations:
        city_chicken_distance = 0
        for home_r,home_c in home_location_list:
            min_home_chicken_distance = sys.maxsize
            for chicken_location in chicken_location_m_combination:
                min_home_chicken_distance = min(
                    min_home_chicken_distance,
                    abs(home_r - chicken_location[0]) + abs(home_c-chicken_location[1])
                )
            city_chicken_distance += min_home_chicken_distance
        min_distance_of_m_combinations = min(min_distance_of_m_combinations,city_chicken_distance)


    return min_distance_of_m_combinations





# 출력
print(get_min_city_chicken_distance(n, m, city_map))  # 5 가 반환되어야 합니다!

for문이 많이들어가서 코드가 안돌아가면 어쩌나 했는데 때론 무식하게 하는게 맞다는걸 느꼈다