❓ 문제 - 백준 치킨 배달 15686번 - python 풀이법
출처
(https://www.acmicpc.net/problem/15686)
📝 문제해결법
1. 이 문제는 BFS(조합)+구현으로 풀었다.
- combination() 함수를 사용하여 기존에 있는 치킨 집에서 m개의 치킨집을 선택하여 해당 치킨집만을 운영했을 때 도시의 치킨 거리를 구하여 도시의 치킨 거리의 최솟값을 갱신해준다.
- find_dist() 함수를 사용하여 현재 집 위치에서 선택된 치킨 집까지의 치킨 거리를 구하고 최소가 되는 치킨 거리를 찾아 도시의 치킨 거리로 합해준다. 또한 구한 도시의 치킨 거리와 min_value 변수를 비교하여 도시의 치킨 거리의 최솟값을 계속 갱신해준다.
💻 소스코드
n, m = map(int, input().split())
graph = []
chicken = []
home = []
for i in range(n):
data = list(map(int, input().split()))
for j in range(n):
if data[j] == 2:
chicken.append([i, j])
elif data[j] == 1:
home.append([i, j])
def combination(lst, num):
result = []
if num > len(lst):
return result
if num == 1:
for i in lst:
result.append([i])
elif num > 1:
for i in range(len(lst)-num+1):
for temp in combination(lst[i+1:], num-1):
result.append([lst[i]]+temp)
return result
min_value = int(1e9)
def find_dis(c):
global min_value
all_c = 0
for h_x, h_y in home:
min_c = 2*n+1
for c_x, c_y in c:
dist = (abs(h_x-c_x) + abs(h_y-c_y))
min_c= min(min_c, dist)
all_c += min_c
min_value = min(min_value, all_c)
for c in combination(chicken, m):
find_dis(c)
print(min_value)
'알고리즘 > 알고리즘문풀' 카테고리의 다른 글
BOJ - 아기 상어 16236번 (python) (0) | 2021.10.16 |
---|---|
BOJ - 나무 재테크 16235번 (python) (0) | 2021.10.16 |
BOJ - 드래곤 커브 15685번 (python) (0) | 2021.10.16 |
BOJ - 사다리 조작 15684번 (python) (0) | 2021.10.15 |
BOJ - 감시 15683번 (python) (0) | 2021.10.15 |