[백준][파이썬] 15686번 - 치킨 배달

[백준][파이썬] 15686번 치킨 배달

문제 번호 : 15686
문제 출처 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

---

Code

import sys
from itertools import combinations

## 입력
n, m = map(int, input().split())
city = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

distance = []   # 집 별로 치킨 집과의 거리 저장
chickens = []   # 치킨 집의 위치와 치킨 집의 번호 저장
houses = []     # 집의 위치 저장
n_chicken = 0
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            houses.append([i, j])
        elif city[i][j] == 2:
            chickens.append([i, j, n_chicken])
            n_chicken += 1

for i in range(len(chickens)):
    distance.append([])
    for house in houses:
        distance[i].append(abs(chickens[i][0] - house[0]) + abs(chickens[i][1] - house[1]))

cases = combinations(chickens, m)

answer = 1e9

for case in cases:
    d = []
    for i in range(m):
        d.append(distance[case[i][2]])

    d = list(map(min, zip(*d)))
    answer = min(sum(d), answer)

print(answer)

Idea

1. N x N 크기의 배열을 모두 탐색하면서 집의 위치와 치킨 집의 위치를 모두 저장
2. 치킨 집의 위치를 저장할 때에는 치킨 집의 number를 차례로 부여
3. 집마다 각 치킨집과의 거리를 저장
4. 치킨 집의 갯수에서 M개의 조합을 생성
5. M개의 조합을 모두 탐색하며 치킨 거리가 최소인 답을 구함

이번 문제에서 zip 함수와 map 함수, 그리고 * 을 사용해서 각 거리들 중 최단 거리를 구했다.
d = list(map(min, zip(*d))) 를 해석해보겠다.
iterable앞에 *을 붙이게 되면 iterable형의 요소들을 모두 반환한다.
예시를 들자면 다음과 같다.

def print_all(a, b, c):
    print(a)
    print(b)
    print(c)

li = [1, 2, 3]
print_all(*li)

### 실행결과
# 1
# 2
# 3

코드에서 d 는 2차원 리스트이므로 여러 개의 1차원 리스트들을 반환한다.
zip함수는 여러개의 iterable이 입력으로 들어오면 index가 같은 요소들끼리 튜플로 합쳐서 반환한다. d의 각 1차원 리스트들은 각 집에서 치킨집들까지의 거리이고 zip함수를 사용하고 나면 각 치킨 집마다의 집들까지의 거리가 된다.
여기에 map함수로 각 리스트별로 min함수를 사용해서 리스트로 반환한다.
처음에 2차원 배열을 모두 돌면서 각 치킨집 별로 최소 거리를 구하는 방법을 사용했고 시간이 400ms가 나왔다. 그런 과정을 저 한 줄의 코드로 변환해서 확인한 결과 112ms로 시간이 많이 줄어들었다.