[문제 풀이] 백준 15686

해결 과정

말 그대로 구현 문제. 어려운 부분은 없었다. 모든 케이스를 모두 탐색하면 된다.

 

 

나의 풀이

from itertools import combinations

def cityChickenDistance(candidate):
    dist = 0

    for h in house:
        minDist = []
        for c in candidate:
            dis = abs(h[0]-c[0]) + abs(h[1]-c[1])
            minDist.append(dis)
        dist += min(minDist)

    return dist

def solution(N, M):
    answer = -1

    markets = [] # markets = [(0, 1), (1, 2)]
    global house
    house = []

    for i in range(N):
        for j in range(N):
            if cities[i][j] == 2:
                markets.append((i, j))
            elif cities[i][j] == 1:
                house.append((i, j))
    
    candidates = list(combinations(markets, M))

    for candidate in candidates:
        cityDist = cityChickenDistance(candidate)
        if answer == -1 or answer > cityDist:
            answer = cityDist

    return answer

# 입력
N, M = map(int, input().split())
cities = [list(map(int, input().split())) for i in range(N)]

print(solution(N, M))