[BAEKJOON]15686 치킨 배달- Python

문제 요약

• 알고리즘 분류:백트레킹
• 난이도: Gold5
• 문제내용:
  • 가로 세로 길이 N, 폐점 안할 치킨 집 M, 지도 2차원 배열
  • 치킨 거리: (x1, y1) ~ (x2, y2) = |x1 - x2| + |y1 - y2|
  • 도시의  각 집과 치킨 집의 치킨 거리의 최소 합 을 구해라
• 사이트: https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

문제풀이

   이번에는 문제 유형은 백트레킹 알고리즘이다. 조합으로 백트레킹 문제를 풀면 되면 조합으로 백트레킹 구현 하는 방법은 아래의 사이트에서 확인 해보면된다.

https://jih3508.tistory.com/30

[BAEKJOON] 15650 N과 M (2)

문제 접근방법

예제 2번으로 6개 집이 있고 치킨 집은 5개 폐점 안 시킬집은 2개가 있다고 가정하자. 위 그림에서 임의로 2개로 맨위에 선택 했다고 보면 각 집에서 두 개의 치킨 집 중 가장 가까운 거리를 구해서 합하면 된다. 위 방법을 치킨 집 2개씩 조합을 짜서 각 경우의 수 만큼 치킨 거리의 합을 구한것중 최소 값을 구하면된다.

1. 집, 치킨 집 각 위치를 구한다.
2. 치킨 집 M개의 조합을 만든다.
3. 각 조합에서 집과 치킨 집의 거리 최소 합을 구한 다음 각 조합에서 가장 작은 값을 출력한다.

Code

Python

import sys
from itertools import combinations

N, M = map(int, input().split())
fields = [list(map(int, input().split())) for _ in range(N)]
houses = []
chicken_houses = []

for i in range(N):
    for j in range(N):
        if fields[i][j] == 1:
            houses.append((i, j))
        if fields[i][j] == 2:
            chicken_houses.append((i, j))

distance = N * 2 * len(houses)
for chicken_house in combinations(chicken_houses, M):
    distances = [N * 2] * len(houses)
    for i in range(len(houses)):
        x1, y1 = houses[i]
        for x2, y2 in chicken_house:
            distances[i] = min(abs(x1 - x2) + abs(y1 - y2), distances[i])
    distance = min(distance, sum(distances))

print(distance)