백준 15686번 치킨 배달 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 15686 치킨 배달

15686 치킨 배달

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

15686번: 치킨 배달

쉬워 보이는 문제 이름과는 다르게 어려웠던 문제였다. 브루트 포스 문제로 모든 조합을 계산하여 집과의 거리가 제일 가까운 m개의 치킨집을 구하고 그 합을 출력하는 문제이다.

---

코드

import sys
from itertools import combinations

input = sys.stdin.readline

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

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


for i in combinations(chicken, m):  # m개의 치킨집 선택
    ccd = 0            # 도시의 치킨 거리 city chicken distance
    for h in house:
        chicken_distance = 999999   # 각 집마다 치킨 거리
        for j in range(m):
            chicken_distance = min(chicken_distance, abs(h[0] - i[j][0]) + abs(h[1] - i[j][1]))
        ccd += chicken_distance
    result = min(result, ccd)

print(result)

---

풀이

우선 인풋 값들을 정리한다. 필자는 maps라는 리스트에 각 행을 리스트로 선언하였다.

ex) [[0, 0, 1, 0, 0], [0, 0, 2, 0, 1] ... ]

 

house (maps에서 1), chicken(maps에서 2) 값을 저장하기 위해 빈 리스트를 선언해준다.

집과 치킨집을 배열에 저장하기 위해 2차원 배열을 다루는 for문 2개를 작성한다.

이후에는 combinations를 활용해 chicken이라는 리스트에서 m개를 뽑는 조합을 만들고 이 조합들을 이용해 모든 집의 치킨 거리를 구하기 위한 for문 2개를 작성한다. 도시의 치킨 거리를 초기화하며 for문을 돌아야 한다.

즉 모든 조합을 돌며 도시의 치킨 거리가 최소인 값을 result에 재 선언하며 비교하고 끝으로 출력하는 것이다.

(result, chicken_distance를 999999로 선언한 이유)

---

풀이 결과

15686 풀이 결과

combinations에 대해 궁금하다면...

https://wikidocs.net/106964

05-06 itertools.combinations - 조합