[이코테] 구현 - 치킨 배달

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 링크를 참조하자.

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

15686번: 치킨 배달

사고과정

• 구현에서 문제가 길어지면 요구사항을 놓치는 경우가 빈번한 것 같다.. 주어진 데이터 범위가 크지 않다고 생각해서 완전 탐색인 것 같다고 생각했다. 그런데 문제에서 요구하는 도시의 치킨 거리라는 것이 각 집과 치킨 거리의 최단 거리의 '합'이라는 것을 잘 이해하지 못했다. 아쉽게도 못 풀었다..
• 풀이 소스코드를 바로 보지 않고 핵심 아이디어만 보고 다시 풀려고 노력했을 때, 원만하게 풀렸다..  폐쇄할 치킨집도 치킨 거리를 기준으로 직접 구현해야 하나했는데, 그냥 치킨집 중 M개의 치킨집 고르는 모든 경우의 수를 완전 탐색하는 방법으로 풀 수 있었다..! 아쉽다..

풀이(스스로 못 푼 풀이)

from itertools import combinations

n, m = map(int, input().split())
chicken, house = [], []
for i in range(n):
    data = list(map(int, input().split()))
    for j in range(n):
        if data[j] == 1:
            house.append((i, j))
        elif data[j] == 2:
            chicken.append((i, j))


# 치킨집 M개 조합 중 1개 경우의 수 당 도시의 치킨 거리 구하기
def get_chicken_dist(chicken_comb):
    result = 0
    # 각 집 당 가장 가까운 치킨집과의 치킨 거리 구하기
    for h_x, h_y in house:
        min_dist = int(1e9)
        for c_x, c_y in chicken_comb:
            dist = abs(h_x-c_x) + abs(h_y-c_y)
            min_dist = min(min_dist, dist)
        result += min_dist
    return result


res = int(1e9)
for comb in list(combinations(chicken, m)):
    res = min(res, get_chicken_dist(comb))

print(res)