백준: 15686 치킨 배달

문제

15686번: 치킨 배달

 

문제 풀이

 크기가 NxN인 도시에서 치킨집과 집이 있을 때, 치킨 집 M개만 선택하고 나머지는 폐업하여야 한다. 이때 도시의 치킨 거리가 가장 작게 되는 경우를 반환하는 문제이다. 문제를 풀기 위해서 아래와 같은 로직을 작성하면 풀 수 있다.

 

• 입력된 NxN에서 도시에서 치킨 집과 집의 좌표를 찾는다.
• DFS를 통해 M개의 치킨집을 선택하고, M개가 선택된 경우 거리를 계산한다.
  • 문제에서 거리를 계산하는 식은 맨하튼 거리이다.

 

코드

from sys import stdin
from math import inf


def manhattan_dist(h, c):
    return abs(h[X] - c[X]) + abs(h[Y] - c[Y])


def dfs(idx, selected):
    global answer

    if idx > len(chicken):
        return

    if selected == m:
        sum_distance = 0
        for house in houses:
            min_distance = inf
            for c_idx, value in enumerate(chicken):
                if not check[c_idx]:
                    continue
                min_distance = min(min_distance, manhattan_dist(house, value))
            sum_distance += min_distance
        answer = min(answer, sum_distance)
        return

    check[idx] = True
    dfs(idx + 1, selected + 1)
    check[idx] = False
    dfs(idx + 1, selected)


if __name__ == '__main__':
    X, Y = 0, 1
    n, m = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().split())) for _ in range(n)]
    houses, chicken = [], []
    answer = inf

    for i in range(n):
        for j in range(n):
            if graph[i][j] == 1:
                houses.append([i + 1, j + 1])
            elif graph[i][j] == 2:
                chicken.append([i + 1, j + 1])
                
    check = [False] * (len(chicken) + 1)
    dfs(0, 0)
    print(answer)

 파이썬의 경우 `itertools.combination`을 사용하여 풀 수 있지만, 삼성 SW 역량 테스트의 경우 `itertools`를 사용할 수 없기에, DFS로 문제를 풀었다.