[백준] 15686 치킨 배달 (파이썬 python)

 

 

문제 링크

 

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

15686번: 치킨 배달

 

 

문제

 

 

 

 

 

문제 풀이

 

 

from itertools import combinations

n, m = map(int, input().split())
chicken, house = [], []
data = []
for _ in range(n):
    data.append(list(map(int, input().split())))
result = 9999

for r in range(n):
    for c in range(n):
        if data[r][c] == 1:
            house.append((r, c))    # 일반 집
        elif data[r][c] == 2:
            chicken.append((r, c))    # 치킨집

for c in combinations(chicken, m):
    temp = 0
    for h in house:
        chicken_len = 9999
        for i in range(m):
            chicken_len = min(chicken_len, abs(h[0] - c[i][0]) + abs(h[1] - c[i][1]))
        temp += chicken_len
    result = min(result, temp)

print(result)

 

 

완전 탐색과 조합을 이용한 풀이이다.

data에 각 위치를 모두 저장한 후

값이 1일 경우 house 리스트에, 2일 경우 chicken 리스트에 위치를 저장한다.

combinations(리스트, m) => 리스트에서 m개의 조합을 뽑아준다!

조합으로 뽑힌 치킨집과 집의 치킨 거리를 찾아 최소의 값을 temp에 더해주는 연산을 모두 마친 후

이들 중 최소의 값을 출력해주면 된다 :)