[BOJ][Python3]15686.치킨 배달

문제 유형: 구현

collection에 combination을 쓰면 된다.

여담이지만 pypy로 채점 돌렸을때 메모리+런타임으로 1등 먹어서 살짝 기분이 좋았다 ㅎㅎ

시간이 지나면 한순간의 꿈일 것 같지만...

 

문제 포인트는 다음과 같다

1) 입력을 받으면서 집, 치킨집 위치를 튜플로 저장해서 배열에 넣어두기 

2) 미리 각 집의 모든 치킨집 위치에 대한 걸 계산해서 배열에 저장해 두기(그렇다면 나중에 치킨집을 고르고 일일히 계산하지 않아도 된다)

3) 치킨집의 경우의 수를 combination으로 뽑고, 각 경우의 치킨 거리 계산하기

 

처음에 문제를 잘못 이해해서 현재 치킨집 수 = 남길 치킨집 수의 경우 일일히 비교하는 로직을 안 쓰고 바로 답을 구하는 모종의 방법을 사용했는데 그 로직에 문제가 있어서 틀렸다고 나왔다.

결국 알고리즘은 엣지케이스의 일반화가 가장 중요한 것 같다. 내가 짜 놓은 로직에 엣지케이스가 걸릴 수 있게 하는 거다.

 

코드는 다음과 같다.

import sys
from itertools import combinations

def sol(cmap, cpos, hops, survival) :
    cnum = len(cpos)
    h_arr = [[0 for _ in range(cnum)] for _ in range(len(hops))]
    #h[i][j] : i번 집이 j번째 치킨집에 대한 치킨거리


    for i in range(cnum):
        col_val = cpos[i][0]
        row_val = cpos[i][1]
        for j in range(len(hops)):
            dir = abs(col_val - hops[j][0]) + abs(row_val-hops[j][1])
            h_arr[j][i] = dir

    clist = list(range(cnum))
    try_list = list(combinations(clist, survival))

    minimum = sys.maxsize

    for i in try_list:
        #한 가지가 뽑히는 조합 구현
        total = 0
        for h in h_arr:          #한 집에서 최소 치킨 거리를 계산하기
            local_minimum = 5000
            for j in i:
                if h[j] < local_minimum:
                    local_minimum = h[j]
            total = total + local_minimum

        if minimum > total :
            minimum = total
    return minimum



N, M = map(int, input().split())
chicken_map = []
house_pos = []
chicken_pos = []

for i in range(N):
    row = list(map(int, input().split()))

    for j in range(N):
        if row[j] == 2:
            chicken_pos.append((i, j))
        if row[j] == 1:
            house_pos.append((i, j))
    chicken_map.append(row)

print(sol(chicken_map, chicken_pos, house_pos, M))