백준 15868 치킨배달 파이썬, 삼성 SW 기출문제

문제 링크 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

도시에 있는 치킨집 중에서 최대 M 개를 골랐을 때, 도시의 치킨 거리를 구하는 문제이다. 

치킨집들 중에서 M 개를 고르는 경우를 구할때 파이썬의 조합 라이브러리를 이용하면 이 문제는 생각보다 쉽게 풀 수 있다 (!)

itertools의 combination을 사용한다 

풀이 과정은 다음과 같다 

1. data 입력을 받는다 

2. for 문으로 data 입력 받을 때 치킨집의 위치 x, y 를 저장한다

3. for 문으로 data 입력 받을 때 집의 위치 x,y 를 저장한다 ->  나중에 다시 일일이 집이랑 치킨집 위치 for문 이중으로 돌면서 확인하는 것보다 비용이 절감된다 ! 

4. combination으로 치킨집들 중에서 m개를 고르는 경우의 수 list를 생성한다 

5. 조합 리스트를 하나씩 순회하면서 최소가 되는 치킨 거리 abs(치킨집의 위치 x좌표 -집의 위치 x좌표) + abs(치킨집의 위치 y좌표 - 집의 위치 y좌표)를 구한다 

6. 최소 치킨거리값을 출력한다 

 

코드로 옮겨보자 

from itertools import combinations

n, m = map(int, input().split())
chicken = []
home = []

for r in range(n): # row 의 길이 n 
    data = list(map(int, input().split()))
    for c in range(n): # column의 길이도 n 
        if data[c] == 2: 
            chicken.append((r, c))
        elif data[c] == 1:
            home.append((r, c))

candidates = combinations(chicken, m)

def solve(candidate):
    result = 0 # 치킨 거리 최종
    for hx, hy in home:
        temp = 1e9
        for cx, cy in candidate:
            temp = min(temp, abs(hx - cx) + abs(hy - cy)) # 한 집에서 가장 가까운 치킨집과의 거리를 구함
        result += temp
    return result

result = 1e9

for candidate in candidates:
    result = min(result, solve(candidate))
print(result)