[Python] 백준 15686 치킨 배달

문제

크기가 N×N인 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나. 도시의 칸은 (r, c)와 같은 형태로 나타낸다.
치킨 거리는 집과 가장 가까운 치킨집 사이의 거리. 치킨 거리는 집을 기준으로 정해지며, 도시의 치킨 거리는 모든 집의 치킨 거리의 합
임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다.

어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성

 

 

입력

• 첫째 줄 :  도시 크기 N(2 ≤ N ≤ 50)과 치킨집 개수 M(1 ≤ M ≤ 13)
• 둘째 줄부터 N개의 줄 : 도시의 정보( 0 : 빈 칸, 1 : 집, 2 : 치킨 집)

 

 

출력

폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값

 

 

---

★Keypoint : 조합 ( combinations)

 

출력해야 하는 답을 봤을 때, 수학 개념인 '조합'을 떠올릴 수 있다.

서로 다른 n개의 물건에서 순서를 생각하지 않고 r개를 택할 때, 이것은 n개에서 r개를 택하는 조합.

각각의 집에서 부터 치킨집까지의 최소 거리인 치킨 거리를 구하고 파이썬 조합 함수를 이용하여 최소값을 갖는 조합 찾기

 

조합을 사용하지 않고 오름차순으로 거리를 정렬하여 m개만큼 추출하는 방법도 고려했으나 for문이 더 중첩될 것 같아 '조합'을 사용했다. 

 

 

<최종 CODE>

from itertools import combinations

n, m = map(int, input().split())
board = []
homes = [] #집의 좌표 리스트
chickens = [] #치킨 집의 좌표 리스트

for _ in range(n):
    board.append(list(map(int, input().split(" "))))

for i in range(n):
    for j in range (n):
        if board[i][j] == 1:
            homes.append((i,j))
        elif board[i][j] == 2:
            chickens.append((i,j))
def checkdist(lst):  # 거리 계산 함수
    totaldist = 0
    for c, d in homes:
        mindist = float('inf')  # 최소 거리 초기값은 최댓값으로 설정
        for a, b in lst:  #치킨 거리 구하기
            dist = abs(a - c) + abs(b - d)
            mindist = min(mindist, dist)
        totaldist += mindist #치킨 거리의 합
    return totaldist

result = float('inf') #초기값으로 큰 값 설정
for s in combinations(chickens, m):
    result = min(result, checkdist(s))

print(result)

 

 

 

<CODE 설명>

abs() 절댓값 구하는 함수와 itertools 의 조합 사용하기

 

문제에서 치킨 거리는 집을 기준으로 구하는 것이라 했으므로, for문을 작성할 때 먼저 homes 리스트에서 반복문을 돌게 하고 그 안에 chickens 리스트 반복문을 돌게 하면서 거리를 구했다.

 

추가적으로 거리를 최소로 만들 때의 치킨집의 위치 또한 궁금했다.

이렇게 마지막 코드를 작성하면 치킨 집 위치까지 출력 가능!

 

 

 

 

※아래는 구현된 조합 알고리즘과 시간복잡도가 나와 있다. n! 정도면 너무 큰데.. 조합 말고 다른 방식으로 시간복잡도를 줄일 수 있는 코드 작성을 시도 해 봐야겠다.

 

https://velog.io/@hyun0820/Python-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EA%B3%B1%EC%A7%91%ED%95%A9-%EC%A4%91%EB%B3%B5-%EC%88%9C%EC%97%B4-%EC%A4%91%EB%B3%B5-%EC%A1%B0%ED%95%A9-%ED%8A%9C%ED%86%A0%EB%A6%AC%EC%96%BC

Python 순열, 조합, 곱집합, 중복 순열, 중복 조합 튜토리얼