파이썬 백준 알고리즘: 치킨 배달 15686

안녕하세요! 알고리즘 풀이 포스트를 작성할 개발자로 도움을 드릴게요. 이번에는 "치킨 배달" 문제를 다루어보려고 합니다. 치킨 배달 문제는 조합과 최소 거리를 구하는 문제입니다.

문제 내용

주어진 도시에서 가장 가까운 거리에 있는 M개의 치킨집을 골라, 치킨 거리의 합이 최소가 되도록 배달 거리를 구하는 문제입니다.

문제 이해하기

주어진 문제를 풀기 위해 조합(Combinations)과 최소 거리를 구하는 로직을 사용합니다.

주어진 코드에서는 main 함수를 통해 문제를 해결합니다. 다음은 코드의 주요 로직입니다.

1. 입력값을 받아 도시의 크기(N)와 선택할 치킨집의 개수(M)를 저장합니다.
2. 도시의 상태를 나타내는 행렬(matrix)을 입력받습니다.
3. **home_set**과 **chicken_set**이라는 두 개의 집합(set)을 생성합니다. 각각은 집과 치킨집의 위치를 저장합니다.
4. answer 변수를 매우 큰 값(1e9)으로 초기화합니다.
5. **chicken_list**는 치킨집의 조합을 나타내는 변수로, **chicken_set**에서 M개의 치킨집을 선택한 조합을 반복적으로 생성합니다.
6. min_sum 변수를 0으로 초기화합니다. 이 변수는 치킨 거리의 합을 저장합니다.
7. **home_i**와 **home_j**는 집의 위치를 나타내며, **home_set**에서 순서대로 가져옵니다.
8. 선택한 치킨집 조합(chicken_list)에 대해 각 집과의 최소 거리를 계산하고, 이를 **min_sum**에 더합니다.
9. 만약 현재까지 구한 최소 치킨 거리(answer)보다 **min_sum**이 크거나 같다면 반복문을 종료합니다.
10. 최소 치킨 거리(min_sum)이 현재까지의 최소 치킨 거리(answer)보다 작다면, **answer**를 **min_sum**으로 갱신합니다.
11. 반복이 종료되면 **answer**를 출력합니다.

풀이 코드

pythonCopy code
import sys
from itertools import combinations

input = sys.stdin.readline

if __name__ == "__main__":
    N, M = map(int, input().split())
    matrix = [list(map(int, input().split())) for _ in range(N)]

    home_set, chicken_set = set(), set()
    for i in range(N):
        for j in range(N):
            if matrix[i][j] == 1:
                home_set.add((i, j))
            elif matrix[i][j] == 2:
                chicken_set.add((i, j))

    answer = int(1e9)
    for chicken_list in combinations(chicken_set, M):
        min_sum = 0
        for home_i, home_j in home_set:
            min_sum += min([abs(home_i - chicken_i) + abs(home_j - chicken_j) for chicken_i, chicken_j in chicken_list])
            if answer <= min_sum:
                break
        if min_sum < answer:
            answer = min_sum
    print(answer)

풀이 방법

1. 입력값인 도시의 크기(N)와 선택할 치킨집의 개수(M)를 받습니다.
2. 도시의 상태를 나타내는 행렬(matrix)을 입력받습니다.
3. **home_set**과 **chicken_set**이라는 두 개의 집합(set)을 생성합니다.
   • **home_set**에는 집의 위치를 저장합니다.
   • **chicken_set**에는 치킨집의 위치를 저장합니다.
4. answer 변수를 매우 큰 값(1e9)으로 초기화합니다.
5. **chicken_list**는 치킨집의 조합을 나타내는 변수로, **chicken_set**에서 M개의 치킨집을 선택한 조합을 반복적으로 생성합니다.
6. min_sum 변수를 0으로 초기화합니다. 이 변수는 치킨 거리의 합을 저장합니다.
7. **home_i**와 **home_j**는 집의 위치를 나타내며, **home_set**에서 순서대로 가져옵니다.
8. 선택한 치킨집 조합(chicken_list)에 대해 각 집과의 최소 거리를 계산하고, 이를 **min_sum**에 더합니다.
9. 만약 현재까지 구한 최소 치킨 거리(answer)보다 **min_sum**이 크거나 같다면 반복문을 종료합니다.
10. 최소 치킨 거리(min_sum)이 현재까지의 최소 치킨 거리(answer)보다 작다면, **answer**를 **min_sum**으로 갱신합니다.
11. 반복이 종료되면 **answer**를 출력합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 조합 생성을 위한 combinations 함수와 최소 거리를 구하는 반복문에 의해 결정됩니다. 주어진 도시의 크기를 N이라고 할 때, 치킨집의 개수 M에 대해 M개의 치킨집 조합을 생성하는 시간 복잡도는 O(N^2 * M)입니다. 최소 거리를 구하는 반복문에서는 집의 개수에 비례하는 시간이 소요되므로 O(N^2)입니다. 따라서 전체적인 시간 복잡도는 O(N^2 * M * N^2)로 표현할 수 있습니다.

이상으로 "치킨 배달" 문제의 개발자 알고리즘 풀이 포스트를 작성해보았습니다. 다른 문제에 대해서도 도움이 필요하신 경우 언제든지 말씀해주세요. 좋은 결과가 있기를 기대하겠습니다!

 

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음