치킨 배달 파이썬 정리/구현 (삼성 코테 기출)

치킨 배달

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

Edge case

1. 문제조건

• 글 읽는데에 시간투자 많이 할 것

---

Code

1. itertools 사용

# 치킨 배달
# 15686
# 22/07/26/16:51
from itertools import combinations

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

h = list()
ch = list()
for r in range(n):
    for c in range(n):
        if g[r][c] == 1:
            h.append([r, c])    # House의 좌표 저장
        elif g[r][c] == 2:
            ch.append([r, c])   # Chicken House의 좌표 저장
            
nch = len(ch)   # 치킨집의 개수

distance = [0] * nch

# 가게 수만큼 행렬을 만들어
# r1, c1 집 좌표
answer = int(1e9)
for cch in combinations(ch, m): # m가지 좌표 추출
    tmp = 0
    for r1, c1 in h:
        min_d = int(1e9)
        for r2, c2 in cch:
            min_d = min(min_d, abs(r2-r1)+abs(c2-c1))
        tmp += min_d
    answer = min(answer, tmp)

print(answer)

---

2. Combination 구현

재귀를 이용한 방법

def combination(arr, n):
    result = []

    if n == 0:
        return [[]]
    
    for i in range(0, len(arr)):	# 1번 루프라 하고
        elem = arr[i]
        rest_arr = arr[i+1 : ]
        for c in combination(rest_arr, n-1):	# 2번 루프라 하면
            result.append([elem]+c)

    return result

• arr = [0, 1, 2, 3] 이고, n = 2 일 때

  • combination([0, 1, 2, 3], 2)

    1번 루프

    • [0]+combination([1, 2, 3], 1)

      1번 루프

      • [0] + ([1] + combination([2, 3], 0))
      • [0] + ([2] + combination([3], 0))
      • [0] + ([3] + combination([], 0))

    • [1]+combination([2, 3], 1)

      • [1] + ([2] + combination([3], 0))
      • [1] + ([3] + combination([], 0))

    • [2]+combination([3], 1)

      • [2] + ([3] + combination([], 0))