[Baekjoon Online Judge] 백준 15686번 치킨 배달(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 15686번 치킨 배달

(Python)

(글쓴날 : 2020.03.28)

 

---

* Baekjoon Online Judge, 백준 15686번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 15686번 치킨 배달

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

2) 풀이 과정

2차원 배열의 인덱스 값이 0일 때 빈칸, 1일 때 집, 2일 때 치킨집이라 쳤을 때, 모든 집에서 가장 가까운 치킨집까지의 거리의 합을 구하는 문제입니다.

사실상, 1과 2가 표시되어 있는 좌표평면에서 모든 1을 기준으로 2까지의 거리의 합이 최소인 경우를 구하는 문제이며 주의해야 할 점은 치킨집 즉, 2의 개수를 문제에서 재 지정해 주므로 2가 있을 수 있는 위치의 조합을 계산해 1과의 최소 거리를 구해야 합니다.

 

저의 경우, 모든 집의 위치와 치킨집의 위치를 먼저 구해놓은 뒤, 치킨집의 개수에 따른 조합을 구했고,

모든 조합의 경우에서 집을 기준으로 치킨집까지의 최소 거리의 합들을 solution 리스트에 저장했습니다.

그 후 min() 함수를 사용해 모든 조합의 경우 중 최소 거리의 합이 가장 작은 값을 구해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
from itertools import combinations as C
 
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
allHouse = []
allChicken = []
 
for i in range(N):
    for j in range(N):
        if arr[i][j] == 1:
            allHouse.append((i, j))
        elif arr[i][j] == 2:
            allChicken.append((i, j))
 
allAliveChickenList = list(C(allChicken, M))
 
solution = []
for aliveChickenList in allAliveChickenList:
    allDistance = 0
    for house in allHouse:
        distance = 9999
        for chickenX, chickenY in aliveChickenList:
            if distance > abs(house[0] - chickenX) + abs(house[1] - chickenY):
                distance = abs(house[0] - chickenX) + abs(house[1] - chickenY)
        allDistance += distance
    solution.append(allDistance)
 
print(min(solution))

---