[백준 15686번] 치킨 배달 - Python으로 구현하기

[백준 15686번] 치킨 배달 - Python으로 구현하기

 

문제 접근

• O(13Cm*N*N)의 시간복잡도로 구할 수 있다.
• 집의 좌표, 치킨집의 좌표를 모두 저장해 둔 뒤, 주어진 공식대로 최단거리를 찾으면 된다

 

생각해볼 점

• 시간복잡도를 고려하지않고 BFS로 접근했다가 실패했다. 시간복잡도를 꼭 고려하기!

 

오답 분석

• 최단 거리 구할 때 시간초과 조심

 

from itertools import combinations as cm
import math

N,M = map(int,input().split())
map_data = [list(map(int,input().split())) for _ in range(N)]
chi = []
home = []
for i in range(N):
    for j in range(N):
        if map_data[i][j]==2:
            map_data[i][j]=0
            chi.append([i,j])
        elif map_data[i][j]==1:
            home.append([i,j])
ans=math.inf
for now_chi in cm(chi,M):
    now_sum=0
    for h in home:
        dist=math.inf
        for k in now_chi:
            dist=min(dist,abs(h[0]-k[0])+abs(h[1]-k[1]))
        now_sum+=dist
    ans=min(ans,now_sum)
print(ans)

 

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!