[python] 백준 15686번 : 치킨배달 (combinations, 선형탐색)

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

15686번: 치킨 배달

 

 

1. 성공한 코드 

from itertools import combinations
import sys

n, m = map(int, input().split())
board = [[] for _ in range(n)]
chickenStore = []
house = []
for i in range(n):
    board[i] = list(map(int, input().split()))

# 치킨집 좌표 저장
for i in range(n):
    for j in range(n):
        if board[i][j] == 2:
            chickenStore.append((i,j))
        if board[i][j] == 1:
            house.append((i,j))

# 치킨 거리 구하기
def getDistance(positions):
    global house
    distance = 0

    for h in house:
        hx = h[0]
        hy = h[1]
        value = 1e9
        for p in positions:
            px = p[0]
            py = p[1]
            dis = abs(hx-px) + abs(hy-py)
            value = min(value, dis)
        distance += value
    return distance


minVal = 1e9
for positions in list(combinations(chickenStore,m)):
    d = getDistance(positions)
    minVal = min(d, minVal)

print(minVal)

 

 

2. 코드 개선

from itertools import combinations
import sys

n, m = map(int, input().split())
chickenStore = []
house = []
# 치킨집, 집 좌표 저장
for x in range(n):
    row = list(map(int, input().split()))
    for y in range(n):
        if row[y] == 2:
            chickenStore.append((x, y))
        elif row[y] == 1:
            house.append((x, y))


# 치킨 거리 구하기
def getDistance(positions):
    distance = 0
    # house : [(0, 0), (0, 4), (1, 0), ... , (4, 0), (4, 4)]
    for hx, hy in house:
        value = 1e9
        for px, py in positions:
            dis = abs(hx - px) + abs(hy - py)
            value = min(value, dis)
        distance += value
    return distance


minVal = 1e9
for positions in list(combinations(chickenStore, m)):
    d = getDistance(positions)
    minVal = min(d, minVal)

print(minVal)