[파이썬] 백준 15686 : 치킨배달 (골드5)

[파이썬] 백준 15686 : 치킨배달 (골드5)

15686번: 치킨 배달

---

문제

---

풀이

0. 방향성 생각

• 치킨집 - 집 거리 모두 구하기
• 선택할 치킨집 고르기
• 모든 경우에 대해서 치킨거리 구하기

1. 입력

from itertools import combinations as C
import sys
input = lambda : sys.stdin.readline().rstrip()

n,m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]

• 입력 받기

 

2. 집, 치킨집 좌표 저장

house,chicken = [],[]
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1: house.append((j,i))
        elif arr[i][j] == 2: chicken.append((j,i))
h,c = len(house),len(chicken)

•  집과 치킨집 좌표를 담는다.

 

3. 딕셔너리 형태로 정리

dist = {i:{} for i in range(h)}
for i in range(h):
    x1,y1 = house[i]
    for j in range(c):
        x2,y2 = chicken[j]
        d = abs(x1-x2)+abs(y1-y2)
        dist[i][j] = d

• dist[집번호][치킨집번호] = 맨해튼거리

 

4. 출력

eliminate = list(C(range(c),m))
answer = []

for eli in eliminate:
    score = 0
    for i in range(h):
        temp = []
        for e in eli:
            temp.append(dist[i][e])
        score += min(temp)
    answer.append(score)
print(min(answer))

• 집 번호 i마다 남아있는 치킨집 eli중 가장 가까운 거리를 선택해서 점수 반환
• score에 각 케이스마다 점수 저장 후 answer에 추가
• answer 최소값 출력

---

전체코드

from itertools import combinations as C
import sys
input = lambda : sys.stdin.readline().rstrip()

n,m = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(n)]

house,chicken = [],[]
for i in range(n):
    for j in range(n):
        if arr[i][j] == 1: house.append((j,i))
        elif arr[i][j] == 2: chicken.append((j,i))
h,c = len(house),len(chicken)

dist = {i:{} for i in range(h)}
for i in range(h):
    x1,y1 = house[i]
    for j in range(c):
        x2,y2 = chicken[j]
        d = abs(x1-x2)+abs(y1-y2)
        dist[i][j] = d

eliminate = list(C(range(c),m))
answer = []

for eli in eliminate:
    score = 0
    for i in range(h):
        temp = []
        for e in eli:
            temp.append(dist[i][e])
        score += min(temp)
    answer.append(score)
print(min(answer))

 

코멘트

이제 이런거 1점오른다....