[알고리즘/백트래킹] 15686번 : 치킨 배달 - python

링크 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

---

• 문제
• 소요시간: 1시간 15분 + 반례 탐색

---

• 설계하기(접근방법) 

1. 입력받기

배열의 크기, 남길 치킨집의 개수

배열을 입력받는다

 

2. 구현하기

조합의 경우의 수를 구할 것인데

백트래킹을 사용하여 시간초과를 방지할 것이다

 

일단 모든 마을에 대해서

모든 치킨집의 거리를 저장한다

 

즉 마을이 4개

치킨집이 3개라면

 distance_list = [ [치킨거리, 치킨거리, 치킨거리 ], [ 치킨거리 , 치킨거리 , 치킨거리 ], [ 치킨거리 , 치킨거리 , 치킨거리 ] , [치킨거리, 치킨거리 , 치킨거리  ] ] 의 형태로

각 리스트에 저장한다

 

만약 이중에서 2개의 치킨집을 고른다면

조합이 치킨집 1, 치킨집2, 치킨집3

중에서

1,2

1,3

2,3 의 형태가 나올 것이다

 

distance_list를 순회하면서 각 조합의 형태로 lst 리스트에 저장을 한후

ex)[[1,3], [2,4], [3,2], [2,4]]을 만들고

만약 리스트의 길이가 남길 치킨집의 개수와 같아지면

각 리스트를 순회하며 min값을 합쳐서 house_ans에 저장한다

 

각 치킨집의 조합 중 가장 작은 값을

 

 

 

그 후 조합을 통해서

 

3. 출력하기

각 치킨집의 조합 중 가장 작은 값을 house_ans에서 출력한다

 

 

---

• 코드(출력)

n , lasts = map(int, input().split())

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

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

distance_list = [[]for _ in range(len(house_lc))]

for i in range(len(house_lc)):
    x,y = house_lc[i]
    for j in range(len(chicken_lc)):
        t_x , t_y = chicken_lc[j]
        distance = abs(x - t_x) + abs(y - t_y)
        distance_list[i].append(distance)

visited = [0 for _ in range(len(chicken_lc))]
house_ans = []
distance_check = [[] for _ in range(len(house_lc))]

#  last = 2개
def dfs(cnt, start, lst):
    ### [2,6], [2,2], [2,4], [5,3], [6,4], [6,4]
    if cnt == lasts:
        ans = 0
        for i in lst:
            ans += min(i)
        house_ans.append(ans)
    else : 
        for i in range(start, len(chicken_lc)):
            if visited[i] == 0:
                visited[i] = 1
                for j in range(len(distance_list)):
                    lst[j].append(distance_list[j][i])
                dfs(cnt + 1, i ,lst)
                visited[i] = 0
                for j in lst:
                    j.pop()

dfs(0, 0, distance_check)

print(min(house_ans))

---

• 얻어갈 부분

1. 백트래킹과 행렬을 조합해서 문제를 풀었다. 반례를 찾고 코드를 고치는데 오랜 시간이 걸렸지만 혼자 힘으로 문제를 풀어냈다. visited 부분에서 실수했는데 주의하자