[Python] 15686번 : 치킨 배달

 

문제 3줄 요약

 

1. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다.

2. 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|

3. 치킨집을 최대 M개 골라 도시의 치킨 거리의 합이 가장 작을 때의 값을 구하라!

 

 

 

 

문제 풀다가 보니

치킨이 먹고싶다는 생각이 들기도 했다.

 

주변에 치킨 집이 참 많은데,

어쩌면 이 문제는 한 번쯤 생각해봤던 문제인 것 같다 ㅋㅋ

 

아무튼

문제로 돌아가서!

 

전에 풀었던 연구소 문제에서 벽을 미리 세워두듯이,

이번 문제에서도 최대 M개인 치킨집을 미리 골라두고

도시의 치킨 거리의 합을 작은 값으로 갱신해주는 방법을 생각하였다.

 

최대 M개의 치킨집은

combination을 이용하여 경우의 수를 모두 고려해주었다.

 

 

from sys import stdin
from itertools import combinations

# 좌표 구조체
class XY:
    def __init__(self, x, y):
        self.x = x
        self.y = y

# 도시의 치킨 거리 계산
def cal_distance(copy_map,bf_list):
    length = len(copy_map)
    chicken_road = 0

    for x in range(length):
        for y in range(length):
            short_d = 0
            if copy_map[x][y] == 1:
                for bf in bf_list:
                    dis = abs(bf.x - x) + abs(bf.y - y)
                    if short_d == 0:
                        short_d = dis
                    else:
                        short_d  = short_d if short_d <= dis else dis
                chicken_road += short_d
    return chicken_road

if __name__ == "__main__":
    # N * N의 도시, 최대 M개의 치킨집
    N, M = map(int, stdin.readline().split())
    chicken_map = []
    chicken_list = []
    visited = []

    min_length = 0

    # 도시 지도 정보 및 치킨집 위치 삽입
    for x in range(N):
        map_info = []
        for y,num in enumerate(map(int, stdin.readline().split())):
            if num == 2:
                chicken_list.append(XY(x,y))
                map_info.append(0)
            else:
                map_info.append(num)
            visited.append(0)
        chicken_map.append(map_info)

    # COMBINATION을 통한 모든 치킨집 경우의 수, 브루트포스 알고리즘
    for bf_list in list(combinations(chicken_list,M)):
        copy_map = chicken_map.copy()
        for bf in bf_list:
            copy_map[bf.x][bf.y] = 2
        if min_length == 0:
            min_length = cal_distance(copy_map, bf_list)
        else:
            cal_d = cal_distance(copy_map, bf_list)
            min_length = cal_d if min_length > cal_d else min_length

    print(min_length)

 

실생활에서 한 번쯤 생각해봤던 고민을

코딩으로 풀어나갔다는게 재밌던 문제였다.

 

연구소 문제를 접하고 푸니

크게 어려움이 없었다.

 

끝!