[백준][구현] 치킨 배달

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

15686번: 치킨 배달

 

내가 작성한 코드

import sys
from itertools import combinations

read = sys.stdin.readline

# get all input
cities = []
chickens = []
N, M = map(int, read().rstrip().split())
for r in range(N):
    for c, v in enumerate(map(int, read().rstrip().split())):
        if v == 1:
            cities.append((r, c))
        elif v == 2:
            chickens.append((r, c))

# get min distance
def distance(city, chicken):
    return sum(abs(x - y) for x, y in zip(city, chicken))

def chicken_distance(cities, chickens):
    chick_dic = 0
    for city in cities:
        chick_dic += min(distance(city, chicken) for chicken in chickens)
    return chick_dic

answer = sys.maxsize
for chickens in combinations(chickens, M):
    answer = min(answer, chicken_distance(cities, chickens))

print(answer)

• 조합
  
  • 치킨집 M개를 고르는 모든 경우의 수
• 브루트 포스
  • 모든 M개의 치킨집에 대한 치킨거리 비교

 

다른 사람이 작성한 코드

from itertools import combinations
 
## 맵크기(N), 치킨집 최대 선택가능개수(M)
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
 
## 빈칸(0), 집(1), 치킨집(2)
house = []
chicken = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 1: house.append((i, j))
        elif board[i][j] == 2: chicken.append((i, j))
 
minv = float('inf')
for ch in combinations(chicken, M):
    sumv = 0
    for home in house:
        sumv += min([abs(home[0]-i[0])+abs(home[1]-i[1]) for i in ch])
        if minv <= sumv: break
    if sumv < minv: minv = sumv
 
print(minv)

• 라인이 더 짧다
  
  • 전체적인 로직은 비슷해보인다

https://juhee-maeng.tistory.com/96

(Python) 백준 15686번: 치킨 배달

기억해야할 것

• [ add(1, y) for y in [1, 2, 3] ]
  
  • 2개의 paramter에 대해 map 사용법