Skip to main content

15686 - 치킨 배달

info
  • 문제 보기: 15686 - 치킨 배달
  • 소요 시간: 16분 30초
  • 풀이 언어: python
  • 체감 난이도: 2️⃣
  • 리뷰 횟수: ✅✅

풀이 키워드​

스포주의

조합 완전탐색


풀이 코드​

info
  • 메모리: 33240 KB
  • 시간: 348 ms
import sys
from itertools import combinations
from math import inf
input = sys.stdin.readline

n, m = 0, 0
table = []
home_pos = []
chicken_pos = []

def solution():
    global n, m, table, home_pos, chicken_pos
    n, m = map(int, input().split())
    for i in range(n):
        data = list(map(int, input().split()))
        for j in range(n):
            if data[j] == 1:
                home_pos.append((i+1, j+1))
            elif data[j] == 2:
                chicken_pos.append((i+1, j+1))
        table.append(data)
        
    combs = list(combinations(chicken_pos, m))
    
    ans = inf
    for comb in combs: # 한 치킨집 위치 세트당
        total_mn = 0
        # 집 위치별 최소 치킨거리 계산
        for hpos in home_pos:
            mn = inf
            for cpos in comb:
                d = abs(hpos[0]-cpos[0]) + abs(hpos[1]-cpos[1])
                mn = min(mn, d)
            
            total_mn += mn
        
        #print(comb, total_mn)
        ans = min(ans, total_mn)
    
    print(ans)

if __name__ == '__main__':
    solution()

풀이 해설​

  1. 집 좌표와 치킨집 좌표를 별도의 리스트에 저장
  2. combinations로 가능한 치킨집 좌표 세트의 리스트 생성
  3. 각 치킨집 좌표 세트별 최소 치킨 거리 계산
  4. 3에서 가장 작게 나오는 거리가 정답

메모​

  • combinations 날먹이 dfs로 조합 구하는 과정을 대체함