백준-15686-치킨 배달

문제

치킨 배달

풀이

문제조건 해석

도시에 있는 치킨집 중 m개의 치킨집을 고르는 문제

도시에 모든 집에 대해 각 집에서 치킨집까지 최단 거리(치킨거리)를 더한 거리(도시의 치킨 거리)를 최소가 되게 m개의 치킨집을 골라야 한다.

알고리즘

처음에는 최단 거리만 생각하고 BFS 써야 하나 생각했다.

그러나, 문제에서 최단거리는 좌표간 가우스 거리로 단순하게 구할 수 있다.

문제의 요점은

1. m개의 치킨집을 고르는 경우에 수에 대해 (조합)
2. 각 도시의 치킨 거리를 구한다
3. 도시의 치킨 거리는 각 집마다의 치킨거리 합으로 구할 수 있다.

코드

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

n, m = [int(x) for x in input().rstrip().split()]
city = []
for _ in range(n):
    city.append([int(__) for __ in input().rstrip().split()])

chicken = []
house = []
for i in range(n):
    for j in range(n):
        if city[i][j] == 2:
            chicken.append((i, j)) # 치킨집들 좌표 배열
        elif city[i][j] == 1:
            house.append((i, j)) # 집들 좌표 배열

MAX_DIST = 2*n
answer = []
for case in combinations(chicken, m): # m개의 치킨집을 고르는 경우
    city_dist = 0 # 도시의 치킨 거리
    for hi, hj in house:
        dist = MAX_DIST # 집마다의 치킨 거리
        for ci, cj in case:
            if dist > abs(ci-hi)+abs(cj-hj):
                dist = abs(ci-hi)+abs(cj-hj)
        city_dist += dist
    answer.append(city_dist)
        
print(min(answer))

배운점

• 최단 거리가 들어있는 문제는 BFS나 DP로만 푸는 것 아니다.
• 다른 사람들은 조합을 DFS로 많이 구현하더라
• 삼성 SW 역량테스트는 브루트포스를 이용한 구현 문제 많다.