백준 15686번 치킨 배달 삼성 SW역량테스트 (Python)

백준 15686번 문제 바로가기

문제 이해

A라는 집과 치킨집과의 거리를 A의 치킨거리라고 한다.
도시에 존재하는 모든 집들의 치킨거리를 합한 값을 도시의 치킨거리라고 한다.
A의 치킨거리는 치킨집들중에 가장 가까운 치킨집과의 거리를 말한다.
치킨집들중에 M개의 치킨집을 제외하고 모두 폐업하려고 한다.
따라서 우리는 여러개의 치킨집중 M개의 치킨집을 고르고 그때의 도시의 치킨거리를 구해야한다.

문제 접근

문제를 보고 3가지로 나누었다.

• 입력을 토대로 치킨집과 집의 좌표를 저장하기
• itertools의 combinations를 통한 조합으로 M개의 치킨집을 고르기.
• M개의 치킨집을 골랐다면 이 때의 도시의 치킨거리 구하고 최솟값 저장하기.

모든 집들과 도시의 치킨거리를 비교하며 진행했다.

문제 풀이

입력을 토대로 치킨집과 집의 좌표를 저장하기

ch - 치킨집들의 좌표 리스트
home - 집들의 좌표 리스트

ch = []
home = []
for i, pan_ in enumerate(pan):
    for j, value in enumerate(pan_):
        if value == 2:
            ch.append((i,j))
        if value == 1:
            home.append((i,j))

itertools의 combinations를 통한 조합으로 M개의 치킨집을 고르기.

ch에 치킨집들의 좌표들이 들어있기 때문에 각각 하나의 치킨집을 가르킨다. 따라서 그 중 M개를 선택하는 combinations를 사용한다.

for chs in combinations(ch,M): # M개의 치킨집 조합으로 선택

M개의 치킨집을 골랐다면 이 때의 도시의 치킨거리 구하고 최솟값 저장하기.

각 집들에 대해서 가장 가까운 치킨집과의 거리를 min_distance에 저장하고 이 min_distance를 city_distance에 더해서 도시의 치킨거리를 구한다.
이렇게 구한 도시의 치킨거리들을 M개의 조합들 중 가장 작은 값을 min_city_distance에 저장한다.

for chs in combinations(ch,M): # M개의 치킨집 조합으로 선택
    city_distance = 0 # 현재 선택한 M개의 치킨집으로 도시의 치킨 거리를 저장할 변수
    for i, value_home in enumerate(home): # 집들의 좌표
        min_distance = float('inf') # 가장 적은 치킨거리를 저장할 변수 선택
        for j, value_ch in enumerate(chs): # 치킨집의 좌표
            distance = abs(value_home[0]-value_ch[0]) + abs(value_home[1]-value_ch[1]) # 치킨집과 집의 거리
            if min_distance>distance: # 치킨집과 집의 가장 최소 거리 선택
                min_distance = distance
        city_distance += min_distance # 최소거리를 도시의 치킨 거리에 합함
    if min_city_distance>city_distance: # M개를 선택할 때마다 가장 작은 도시 치킨 거리를 저장함
        min_city_distance=city_distance

제출 코드

import sys
from itertools import combinations
N, M = map(int, sys.stdin.readline().split())
pan = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] 
# 각 치킨집의 치킨거리 구하기
# 오름차순 정렬 후 M개까지 선택 itertool.combinations
# 나머지 폐업
ch = []
home = []
for i, pan_ in enumerate(pan):
    for j, value in enumerate(pan_):
        if value == 2:
            ch.append((i,j))
        if value == 1:
            home.append((i,j))
ch_distance = [[] for i in range(len(home))]
min_city_distance = float('inf') # 도시의 치킨 거리 저장할 변수
for chs in combinations(ch,M): # M개의 치킨집 조합으로 선택
    city_distance = 0 # 현재 선택한 M개의 치킨집으로 도시의 치킨 거리를 저장할 변수
    for i, value_home in enumerate(home): # 집들의 좌표
        min_distance = float('inf') # 가장 적은 치킨거리를 저장할 변수 선택
        for j, value_ch in enumerate(chs): # 치킨집의 좌표
            distance = abs(value_home[0]-value_ch[0]) + abs(value_home[1]-value_ch[1]) # 치킨집과 집의 거리
            if min_distance>distance: # 치킨집과 집의 가장 최소 거리 선택
                min_distance = distance
        city_distance += min_distance # 최소거리를 도시의 치킨 거리에 합함
    if min_city_distance>city_distance: # M개를 선택할 때마다 가장 작은 도시 치킨 거리를 저장함
        min_city_distance=city_distance

print(min_city_distance) #출력