[Baekjoon] 15686번: 치킨 배달 (구현 Gold5) - Python

1. 문제

---

치킨 배달

2. 풀이

---

코드

from itertools import combinations

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]

houses = []
chickens = []

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

min_distance = float('inf')

for selected_chickens in combinations(chickens, m):
    city_chicken_distance = 0
    for house in houses:
        chicken_distance = float('inf')
        for chicken in selected_chickens:
            distance = abs(house[0] - chicken[0]) + abs(house[1] - chicken[1])
            chicken_distance = min(chicken_distance, distance)
        total_distance += chicken_distance
    min_distance = min(min_distance, city_chicken_distance)

print(min_city_chicken_distance)

입력 및 출력

5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

>> 10

3. 로직

---

1. 입력값으로는 n과 m을 받는다. n은 격자판의 크기이고, m은 선택할 치킨집의 개수이다.

2. grid라는 2차원 리스트를 생성하여 격자판의 정보를 입력받는다. 각 요소는 해당 위치의 값(0, 1, 2)을 나타낸다. 0은 빈 공간, 1은 집, 2는 치킨집을 의미한다.

3. houses와 chickens라는 빈 리스트를 생성한다. houses는 집의 위치를 저장할 리스트이고, chickens는 치킨집의 위치를 저장할 리스트이다.

4. 격자판을 순회하면서 집과 치킨집의 위치를 각각 houses와 chickens에 추가한다.

5. 최소 도시의 치킨 거리를 구하기 위해 min_distance 변수를 무한대로 초기화한다.

6. combinations(chickens, m)를 사용하여 선택할 치킨집의 조합을 만든다. 선택된 치킨집의 조합을 selected_chickens로 나타낸다.

7. 각 조합마다 도시의 치킨 거리를 계산한다. houses의 모든 집에 대해 선택된 치킨집과의 거리를 계산하여 치킨 거리를 구하고, 이를 total_distance에 누적합한다.

8. 현재 조합에 대한 도시의 치킨 거리 total_distance를 최소 도시의 치킨 거리 min_distance 와 비교하여 최소값을 갱신한다.

9. 모든 조합에 대해 계산을 완료하면 최소 도시의 치킨 거리 min_distance 를 출력한다.