[스파르타] 99클럽 코테스터디 4일차 TIL / 백준 15686

15686번: 치킨 배달 (링크)

15686번: 치킨 배달

 

백트래킹 문제지만 다른 블로그 풀이를 참고해서 파이썬 combination으로 풀었다.

파이썬 조합 라이브러리 사용법을 좀 더 알아둬야겠다. 

 

(1) 데이터 입력받기

(2) 전체 그래프를 돌면서 1(집), 2(치킨집)의 좌표를 찾음

(3) combination을 이용해서 집 ~ 치킨집 사이의 최소 거리를 찾음

 

from itertools import combinations
import sys

# 1. 데이터 입력 받기
n, m = map(int, sys.stdin.readline().split())
graph = []
chicken = []
city = []

for _ in range(n):
  graph.append(list(map(int, sys.stdin.readline().split())))
  

# 2. graph에서 1, 2가 있는 좌표 찾기
for i in range(n):
  for j in range(n):
    if graph[i][j] == 1:
      city.append([i, j])
    elif graph[i][j] == 2:
      chicken.append([i, j])

      
# 3. combination을 이용하여 치킨집의 모든 경우의 수를 구한 뒤, 최소거리 비교하기
result = 99999
for i in combinations(chicken, m):
  temp = 0 # 도시 치킨 최소 거리
  for house in city:
    chicken_dist = 999
    for j in range(m):
      chicken_dist = min(chicken_dist, abs(house[0]-i[j][0]) + abs(house[1]-i[j][1]))
    temp += chicken_dist
  result = min(result, temp)

print(result)

 

오늘의 미들러 풀이 끝!

 

---

참고한 블로그: https://codesyun.tistory.com/185

[BOJ / 백준] 15686번 치킨 배달 파이썬(Python) 문제 풀이