[Python] 백준 15686번 문제 풀이 - 치킨배달

문제 링크

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

문제 이해

전체 치킨집에서 가게유지비용 때문에 남길 치킨집을 m개로 정했을 때 모든 집에서 치킨집까지의 거리가 최소가 되는 집을 구하고, 최소거리를 출력하는 문제입니다.

집과 치킨집과의 거리는 집과 치킨집의 행과 열의 차이를 더한 것으로 |치킨집x-집x| + |치킨집y-집y| 입니다.

아이디어

최적의 치킨집이 뭔지 찾으려면 어떻게 해야할까 생각하다가 딱히 규칙이 보이지 않았고 전부 탐색을 해봐야겠다고 생각했습니다.

그래서 치킨집의 좌표와, 집의 좌표를 저장해두고 전체 치킨집에서 m개를 뽑는 모든 경우의 수를 탐색하여 최소거리가 나오는 것을 출력하려는 아이디어를 세웠습니다.

그래서 나온 아이디어는 다음과 같습니다.

1. 입력에서 집의 좌표와 치킨집의 좌표를 저장한다.(1과 2가 나오면 저장배열에 저장)
2. 전체 치킨집에서 m개를 뽑는 모든 경우의 수를 탐색한다.
3. m개를 뽑았을 경우에 이 경우가 최소 치킨거리인지 확인한다.
   1. 각 집에서 고른 치킨집까지 가장 적게 걸리는 거리를 저장
   2. 각 집에서 치킨집까지 걸리는 거리를 전부 더해서 최소값인지 판단해서 저장
4. 최소 치킨거리를 출력한다.

시간복잡도

전부 탐색하는 방법을 선택했기 때문에 아이디어를 떠올리며 시간복잡도를 계산했습니다.

우선 치킨집은 최대 13개이고 이중에서 m개를 선택하는 것인데 고르는 경우의 수는 조합의 경우의 수인 13Cm 이 됩니다.

이것을 최대로 만드는 m값은 6또는 7인데 1716이 나옵니다.

그리고 이제 최소거리를 측정해야하는데 집의 거리는 2N개로 100개입니다.

그리고 치킨집은 7일 때 가장 많아집니다.

그래서 정리하면 1716번의 경우에 100번의 집을 탐색하고 치킨집은 7번이기 때문에

1716 X 100 X 7이 되어서 1,201,200이 나오게 되고 이것은 가능합니다.

코드 구현

이 아이디어를 코드로 구현하면 다음과 같습니다.

# 현재 뽑은 치킨집 좌표에서 가장 최소거리 뽑아내는 함수
def update_min_distance(picked_chicken):
    global house_length
    # 치킨집과의 거리 저장 배열
    chicken_house_distance = [int(1e9)] * house_length

    for i in range(house_length):
        (hy, hx) = house_coordinate[i] # 집 좌표 뽑기

        for j in picked_chicken:
            (cy, cx) = chicken_coordinate[j] # 치킨 좌표 뽑기
						
	    # 집에서 치킨집까지의 최소거리 저장
            chicken_house_distance[i] = min(abs(hy-cy) + abs(hx-cx), chicken_house_distance[i])

    return sum(chicken_house_distance) # 총 치킨거리 리턴

# 전체 치킨집 중 m개 치킨집 빼기 위한 재귀함수
def recur(start):
    global answer
    global chicken_length

    # m개 뽑았으면 최소값 리턴
    if len(picked) == m:
        answer = min(answer, update_min_distance(picked))
        return

    # 남아있는 거
    remain = chicken_length-start
    # 필요한 거
    need = m - len(picked)
    # 남아있는거보다 필요한게 더 많으면 리턴
    if remain < need:
        return

    # m개 배열에 넣는 재귀함수
    for i in range(start, chicken_length):
        picked.append(i)
        recur(i + 1)
        picked.pop()

import sys
input = sys.stdin.readline

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

# 치킨집 좌표
chicken_coordinate = []
# 집 좌표
house_coordinate = []

for i in range(n):
    temp = list(map(int, input().split()))

    for j in range(n):
        if temp[j] == 1: # 집 좌표 저장
            house_coordinate.append((i,j))
        elif temp[j] == 2: # 치킨집 좌표 저장
            chicken_coordinate.append((i,j))

house_length = len(house_coordinate)
chicken_length = len(chicken_coordinate)

picked = []
answer = int(1e9)

recur(0)
print(answer)

 

 

 

느낀 점

이걸 Combination을 써서 조합으로 하면 편하겠다는 생각을 했지만 조합 사용법에 대해 잘 몰라서 재귀함수로 전체 치킨집중에 m개를 뽑는 것을 구현했습니다.

재귀함수를 구현하면서도 어떻게 구현해야 모든 경우를 다 탐색할 수 있는지 떠올리는 것이 어려웠고, 오랜 시간이 걸렸습니다.

그래서 다른 사람이 Combination을 활용하여 푼 풀이를 봤습니다.

import sys
from itertools import combinations

input = sys.stdin.readline

n, m = map(int, input().split())
city = list(list(map(int, input().split())) for _ in range(n))
result = 999999
house = []      # 집의 좌표
chick = []      # 치킨집의 좌표

for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            house.append([i, j])
        elif city[i][j] == 2:
            chick.append([i, j])

for chi in combinations(chick, m):  # m개의 치킨집 선택
    temp = 0            # 도시의 치킨 거리
    for h in house: 
        chi_len = 999   # 각 집마다 치킨 거리
        for j in range(m):
            chi_len = min(chi_len, abs(h[0] - chi[j][0]) + abs(h[1] - chi[j][1]))
        temp += chi_len
    result = min(result, temp)

print(result)

콤비네이션을 사용해서 코드가 엄청 간결했고, 보기 편했습니다.

그래서 조합을 사용하는 방법에 대해 공부를 해봐야겠다고 느꼈습니다.

조합과 순열

우선 파이썬은 itertools의 combinations 함수를 제공합니다. 사용 예시는 다음과 같습니다.

• combinations(iterable, r)

from itertools import combinations

# 예시 리스트
data = [1, 2, 3, 4]

# 2개씩 뽑는 조합
result = list(combinations(data, 2))
print(result) # [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

이렇게 중복을 허용하지 않아 (1,1) 같은 결과는 나오지 않고, 순서를 무시하여 (1,2)와 (2,1)은 나오지가 않습니다.

그리고 반환값은 tuple을 반환해서 이것을 배열로 바꾸려면 list()를 씌워야 합니다.

 

그리고 첫번째 인자에 들어갈 수 있는 값은 반복 가능한 값 이라면 전부 가능합니다.

리스트, 문자열, 튜플, 집합, 딕셔너리 등이 들어갈 수 있습니다.

딕셔너리는 key만 빼서 반복을 돌립니다. 예시를 들면 다음과 같습니다.

print(list(combinations({"a": 1, "b": 2, "c": 3}, 2)))
# [('a', 'b'), ('a', 'c'), ('b', 'c')]

combinations는 중복을 허용하지 않는 조합인데 중복을 허용하는 조합도 사용할 수 있습니다.

 

• combinations_with_replacement(iterable, r)

이 함수도 combinations()와 들어가는 인자는 동일합니다.

from itertools import combinations_with_replacement

data = [1, 2, 3]

result = list(combinations_with_replacement(data, 2))
print(result) # [(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]

이러면 (1,1)과 (2,2) 같은 중복을 허용하는 값도 나오는 것을 확인할 수 있습니다.

 

그리고 순열 사용법에 대해서 알아보겠습니다.

순열은 다음 함수를 사용합니다.

• permutations(iterable, r)

from itertools import permutations

data = [1, 2, 3]
result = list(permutations(data, 2))
print(result) # [(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]

순열은 순서를 신경써서 출력합니다. 그래서 (1,2)와 (2,1)이 있는 것을 확인할 수 있습니다.

하지만 이 순열은 중복을 허용하지 않습니다. 만약 중복이 허용되는 함수를 쓰려면 Product 함수를 사용해야합니다.

 

마지막으로 product 함수 사용법에 대해 알아보겠습니다.

• product(iterable, repeat=N)

from itertools import product

data = [1, 2, 3]
result = product(data, repeat=2)
print(list(result))
# [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

이것도 마찬가지로 인자는 비슷하게 들어가는데요, 두번째 인자에 repeat=N 을 써주어야 하는 점이 약간 다릅니다.

product()는 중복과 순서를 모두 허용하여 출력하여 (1,1) 같은 것도 나오고 (1,2), (2,1) 같은 것도 출력되는 것을 볼 수 있습니다.

 

그래서 각 함수의 특징에 대해 정리하면 다음과 같습니다.

함수종류	순서	중복
combinations	X	X
combinations_with_replacement	X	O
permutations	O	X
product	O	O