문제
처음 이 문제를 접했을 때 어떤 알고리즘으로 문제를 풀어야 할 지 뚜렷하게 생각나는 부분이 없어서 일단 주어진대로 구현을 해야겠다고 생각했다.
집의 좌표와 치킨집의 좌표를 따로 리스트에 각각 저장해야겠다는 생각까지는 했으나 파이썬으로 combination을 사용하는 방법을 잘 몰라서 쉽지않게 느껴졌다.
그래서 사용법을 구글링 한 후 적용시켜서 문제를 해결했다.
나의 코드
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
home = []
chicken = []
#치킨집과 집이있는 좌표의 값을 따로 리스트에 받아줌
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
home.append([i+1,j+1])
if graph[i][j] == 2:
chicken.append([i+1,j+1])
from itertools import combinations
ans = float('inf')
for c in combinations(chicken,m):
#m개의 치킨집 고르는 것 반복
temp = 0
for h in home:
#각각의 집에서 가장 가까운 치킨집의 치킨거리 구함
cd = float('inf')
for j in range(m):
cd = min(cd,abs(h[0]-c[j][0])+abs(h[1]-c[j][1]))
#해당 집에서 가장 가까운 치킨집의 치킨거리 도시의 치킨거리에 구해줌
temp += cd
#구한 도시의 치킨거리중 최솟값 구함
ans = min(ans,temp)
print(ans)각각의 집에서 치킨거리를 구하고 저장하는 부분까지는 쉬운데
도시전체의 치킨거리가 최소가 되도록 m개의 치킨집을 고르는 부분이 어려웠던 문제였던 것 같다.
combination이 꽤나 유용해서 사용법을 잘 익혀두면 앞으로 문제 푸는데에 많은 도움이 될 것같다.
