백준 15686 치킨 배달

문제

치킨 배달

치킨 거리를 구하자

난이도 : Gold5

---

풀이

1. M개의 치킨집을 남기는 조합을 구한다.
2. 한 집에 대해 모든 치킨집과의 거리를 구하고 최소가 되는 거리를 저장

---

코드

import sys
import itertools

n, m = list(map(int, sys.stdin.readline().split()))
data = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dis_list = []  # 거리 저장
ones = [(i, j) for i in range(n) for j in range(n) if data[i][j] == 1]  # 집 좌표 리스트
twos = [(i, j) for i in range(n) for j in range(n) if data[i][j] == 2]  # 치킨집 좌표 리스트

for two in itertools.combinations(twos, m):  # 가능한 m개의 치킨집 조합
    dis = 0  # 각 조합 결과 case별 총 거리를 저장하는 변수
    for one in ones:
        temp = []  # 한 집과 모든 치킨집 사이의 거리를 저장하고, min값을 뽑아 한 집에서 가장 가까운 치킨 집과의 치킨 거리를 구한다.
        for t in two:
           temp.append(abs(t[0] - one[0]) + abs(t[1] - one[1]))
           
        dis += min(temp)
    dis_list.append(dis)
    
print(min(dis_list))

        

---

결과

처음에 좌표가 나오길래 생각도 안하고 bfs를 구현했다. 1에서 bfs를 탐색하며 가장 빨리 만나는 2와의 거리를 치킨 거리로 계산했다. 그러자 시간 초과가 떴다.
그 후 완전 탐색으로 거리를 구하고, 해결했다.
조합을 구할 때 직접 구현하려다 어려워서 itertools를 활용했는데, 자주 등장하는 만큼 라이브러리 함수에 의존하지 말고 직접 구현을 시도해야겠다.