문제
https://www.acmicpc.net/problem/15686
주요 아이디어
- 치킨 거리 = 맨해튼 거리 = L1 norm
- 선택될 수 있는 치킨 집은 최대 13개이므로, 브루트포스 (=완전 탐색) 방식을 통해 치킨 집을 선택하는 모든 경우의 수를 구한 다음 각각의 최소 거리를 구하면 된다
코드 구현 (Python 3)
더보기
"""
크기 N*N
브루트포스
1. 치킨 거리 구하는 함수
2. 치킨 집 위치 좌표 넣기
3. 해당 치킨 집 위치를 제외하고 모두 없앤 가상맵 생성 함수
3. 가상 하나씩 돌면서 모든 경우의 수에 대해 치킨 거리를 계산
"""
from itertools import combinations
import sys
def chicken_dist(r1, c1, r2, c2):
return abs(r1 - r2) + abs(c1 - c2)
# 해당 맵에서의 치킨 거리 합
def calc_sum_dist(stores):
global houses, N
sum_dist = 0
for house in houses:
min_dist = 10**6
for store in stores:
# 집과 가장 가까운 치킨집 거리
min_dist = min(min_dist, chicken_dist(house[0], house[1], store[0], store[1]))
sum_dist += min_dist
return sum_dist
chicken_store = []
houses = []
N, M = map(int, input().split())
graph = [[int(i) for i in sys.stdin.readline().split()] for _ in range(N)]
# print(graph)
min_dist = 10**6
for i in range(len(graph)):
for j in range(len(graph[0])):
if graph[i][j] == 2:
chicken_store.append([i, j])
elif graph[i][j] == 1:
houses.append([i, j])
chicken_combi = list(combinations(chicken_store, M))
# 전체 맵에서의 치킨 거리 합
for stores in chicken_combi:
min_dist = min(min_dist, calc_sum_dist(stores))
print(min_dist)
제출 결과
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 3190. 뱀 (0) | 2024.06.25 |
---|---|
[BOJ] 2630. 색종이 만들기 (0) | 2024.06.25 |
[BOJ] 15683. 감시 (1) | 2024.05.21 |
[BOJ] 13414. 수강신청 (0) | 2024.05.21 |
[BOJ] 1806. 부분합 (0) | 2024.05.21 |