[백준] 15686번 : 치킨 배달

문제

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

풀이

[백준] 15686 : 치킨 배달 🥇(골드5)
🎯 45.619%

• [Combination]

<✅ 문제 요약>

0. $N \times N$ 도시
1. 0은 빈 칸, 1은 집, 2는 치킨집이다.
2. 치킨 거리: 집과 가장 가까운 치킨집 사이의 거리

<✅ 출력>

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

<✅ 풀이방법 & Combination으로 푼이유?>

0.집과 치킨집의 좌료를 각각 리스트에 저장
1. M개의 치킨집 선택하는 것이 관건 combination을 통해 가능한 조합중에 min이 되는 것을 추출한다.

코드(code)

import sys
from itertools import combinations
input = sys.stdin.readline

N, M = map(int, input().split())
# 0은 빈 칸, 1은 집, 2는 치킨집이다.

graph = [list(map(int,input().split())) for _ in range(N)]
house= []
chicken =[]
answer = (N+1)**5

# 각각의 집좌표 치킨 좌표 저장
for x in range(N):
    for y in range(N):
        if graph[x][y] == 1:
            house.append((x,y))
        elif graph[x][y] == 2:
            chicken.append((x,y))

# M개의 치킨집 선택하는 것이 관건 combination을 통해 가능한 조합중에 min이 되는 것을 추출한다.
for chi in combinations(chicken,M): # M개의 치킨집 선택
    total_distance = 0 # 계속 비교할 총 거리 
    for (xh,yh) in house:
        distance = (N+1)*(N+1)
        for (xc,yc) in chi:
            curr_distance = abs(xh-xc)+abs(yh-yc)
            distance = min(distance, curr_distance)
        total_distance +=distance
    answer = min(answer, total_distance)

print(answer)

회고

Combination을 통해서 각 경우의 수로 접근해서 문제를 풀 수 있다는 것을 깨달았다.
다음번에 적용해보자!!

• [해당 코드]

  https://github.com/joejames0830/ps_study/blob/main/Implementation/15686(%EC%B9%98%ED%82%A8%20%EB%B0%B0%EB%8B%AC).py