[백준 15686] 치킨 배달 - python (solved.ac - 골드 5)

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

15686번: 치킨 배달

풀이

문제를 보았을때 알수있는 힌트

문제 자체는 어렵지 않은 문제였습니다. 처음에 보고 그래프로 푸는 문제인가?! 하고 생각했는데 보니까 최소값인 치킨집을 선택하고 집에서 거리를 계산하여 최소가 되는 길이를 찾는 형식의 문제였습니다. 또한 n,m의 최대가 50, 13 이여서 반복이 조금 들어가도 시간 초과는 안나겠다는 생각을 가지고 편하게 풀었습니다.

먼저  그래프에서 치킨집과 일반 집의 위치를 각각 리스트에 뽑았습니다.

다음으로는 치킨집의 개수인 n의 개수만큼의 조합을 리스트로 만들었습니다.

이렇게 생성된 치킨집 조합 리스트를 통해 일반 집까지의 길이를 비교하여 저장해 두고 치킨집별로 가까운 거리를 리스트에 계속 담기게 하였습니다.

담긴 리스트의 합이 최소가 되는 조합이 출력으로 나오게 하여 정답을 받을 수 있었습니다.

 

import sys
from itertools import combinations
input = sys.stdin.readline

n,m= map(int,input().split())
graph = [list(map(int,input().split())) for _ in range(n)]
chicken = []
home = []
result = 1e9
for i in range(len(graph)):
    for j in range(len(graph[i])):
        if graph[i][j]==2:
            chicken.append([i,j])
        elif graph[i][j]==1:
            home.append([i,j])

chicken_com = list(combinations(chicken,m))
for i in chicken_com:
    temp=[1e9]*len(home)
    for j in range(len(home)):
        for k in i:
            temp[j] = min(temp[j],abs(k[0]-home[j][0])+abs(k[1]-home[j][1]))
    result = min(result,sum(temp))
print(result)

 

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon15686.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리