[백준] 15686번: 치킨 배달(골드5, 파이썬)

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

15686번: 치킨 배달

 

아이디어

1. 우선 모든 집과 치킨 집의 좌표를 찾아준다.
2. 치킨 집 M개를 선택한 경우를 모두 구해준다. (dfs 사용)
3. 각 경우의 수에 해당하는 도시의 치킨 거리를 모두 구하고 그 중 가장 작은 값을 구한다.

구현하기 전에는 쉬워보였는데 1시간 32분 걸렸다.. 

 

모든 집과 치킨 집의 좌표 찾기

houses = []
chickens = []

for i in range(N):
    for j in range(N):
        if maps[i][j] == 1:
            houses.append((i+1, j+1))
        elif maps[i][j] == 2:
            chickens.append((i+1, j+1))

맵을 전부 돌면서 1이면 houses에, 2면 chickens에 추가해주었다. 

 

치킨 집 M개를 선택한 경우를 모두 구하기

해당 부분이 떠올리기 제일 어려웠다.

c = []
def getChickens(tmp_chickens, result_chickens):
    global M, c

    if len(result_chickens) == M:
        c.append(copy.deepcopy(result_chickens))
        return
    
    elif len(tmp_chickens) == 0: return
    
    tmp = copy.deepcopy(tmp_chickens)

    while tmp:
        r = copy.deepcopy(result_chickens)
        r.append(tmp.pop(0))
        getChickens(tmp, r)
        

getChickens(chickens, [])

 

우선 두 가지 리스트를 정의해주었다.

tmp_chickens는 남은 치킨 집 위치가 저장되는 리스트이고

result_chickens는 현재 선택한 치킨 집 위치가 저장되는 리스트이다.

만약 현재 M개를 선택했다면 리스트 c에 result_chickens를 추가한 후 return하고, (리스트 c는 선택한 경우가 모두 저장되는 리스트이다.)

선택할 수 있는 치킨이 더 없다면 그냥 return 한다. 

 

경우를 구하는 로직은 다음과 같다.

1. tmp_chickens의 0번을 빼서 result_chickens에 추가한다. 
2. 업데이트된 두 리스트로 함수를 다시 호출한다. 
3. 만약 종료 조건에 해당해서 return된다면, result를 다시 원래 상태로 되돌린다. 
4. 1~3을 tmp_chickens만큼 반복한다.

 

만약 찾은 치킨 집의 좌표가 (1,1), (2,2), (3,3), (4,4), (5,5) 5개이고, m이 3이라고 가정해보자.

각 좌표를 그냥 1,2,3,4,5로 두고 생각하면 

1

1 2

1 2 3 -> c에 append  후 return

1 2 4 -> c에 append  후 return

1 2 5 -> c에 append  후 return

1 3

1 3 4 -> c에 append  후 return

1 3 5 -> c에 append  후 return

1 4

1 4 5 -> c에 append  후 return

1 5    --> 그냥 return 

2

2 3 

2 3 4 -> c에 append  후 return

2 3 5 -> c에 append  후 return

2 4 

2 4 5 -> c에 append  후 return

2 5    --> 그냥 return 

3 

3 4

3 4 5 -> c에 append  후 return

4 

4 5    --> 그냥 return 

5       --> 그냥 return 

 

이러한 절차를 거치게 된다.

 

가장 작은 도시의 치킨 거리 구하기

answer = 1e9

for cc in c:
    total = 0
    for i, j in houses:
        min_distance = 1e9
        for x, y in cc:
            tmp_min_distance = (abs(i-x) + abs(j-y))
            min_distance = min(min_distance, tmp_min_distance)
        
        total += min_distance
    answer = min(answer, total)
    
print(answer)

 

해당하는 경우의 수 만큼 도시의 치킨 거리를 모두 구한다.

도시의 치킨 거리를 구할 때는, 집을 기준으로 모든 치킨 집을 순회하며 치킨 거리(가장 작은 거리)를 먼저 구하고, 더한다.

각 경우에 해당하는 도시의 치킨 거리를 모두 구했으면, 그 중 가장 작은 값을 출력해준다.

 

 

전체 코드

# 10:30 ~ 12:02 (1'32")
import copy
N, M = map(int, input().split())

maps = [[int(x) for x in input().split()] for _ in range(N)]

houses = []
chickens = []

for i in range(N):
    for j in range(N):
        if maps[i][j] == 1:
            houses.append((i+1, j+1))
        elif maps[i][j] == 2:
            chickens.append((i+1, j+1))



c = []
def getChickens(tmp_chickens, result_chickens):
    global M, c

    if len(result_chickens) == M:
        c.append(copy.deepcopy(result_chickens))
        return
    
    elif len(tmp_chickens) == 0: return
    
    tmp = copy.deepcopy(tmp_chickens)

    while tmp:
        r = copy.deepcopy(result_chickens)
        r.append(tmp.pop(0))
        getChickens(tmp, r)
        

getChickens(chickens, [])

answer = 1e9

for cc in c:
    total = 0
    for i, j in houses:
        min_distance = 1e9
        for x, y in cc:
            tmp_min_distance = (abs(i-x) + abs(j-y))
            min_distance = min(min_distance, tmp_min_distance)
        
        total += min_distance
    answer = min(answer, total)
    
print(answer)