핵심 아이디어

  1. NM짜리 이차원 배열을 이용해 최소 치킨 거리를 구한다.
  2. 백트랙을 이용해 M개 집 치킨거리를 구한다.

구현

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

n, m = list(map(int, input().split()))

city = []
for _ in range(n):
    city.append(list(map(int, input().split())))

houseList = []
chickenList = []

for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            houseList.append([i,j])
        if city[i][j] == 2:
            chickenList.append([i,j])

houseChicken = [[0] * len(chickenList) for _ in range(len(houseList))]
for i in range(len(houseList)):
    for j in range(len(chickenList)):
        houseChicken[i][j] = abs(houseList[i][0] - chickenList[j][0]) + abs(houseList[i][1] - chickenList[j][1])

chickenDistance = 123456789
def bfs(index, choosen):
    global chickenDistance
    if index > len(chickenList):
        return
    
    if len(choosen) == m:
        minVal = 0
        for i in range(len(houseList)):
            localMin = 123456789
            for j in choosen:
                localMin = min(houseChicken[i][j], localMin)
            minVal += localMin
        chickenDistance = min(minVal, chickenDistance)
        return
    
    
    bfs(index + 1, choosen)
    choosen.append(index)
    bfs(index + 1, choosen)
    choosen.pop()
    
bfs(0, [])
print(chickenDistance)

아쉬운 점

  • 범위 실수가 많았다.
    • iteration 도는 횟수등 주의하자.

잘한점

  • 시간 복잡도를 먼저 구했다.