[Python] 백준 15686 (구현)

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

15686번: 치킨 배달

개요

• dfs를 닮은 단순 구현 문항
• itertools의 combinations (조합) 을 알면 간단히 해결 가능
• (번외) 3중 for문에 함수 참조까지 섞여 있는데 타임 오버가 안나온게 신기

해결 방법

sys 모듈

• 사용된지 꽤 되어서 그런지 사용법이 잘 기억이 안남
• 사용 이유는 아마 input 함수의 시간 초과율이 높기 때문

import sys

// 두 숫자가 주어질 때 단순히 분리해서 변서에 저장하는 경우
// 5 3 -> n = 5, m = 3

n, m = map(int, sys.stdin.readline().split())

// 배열의 형태로 저장해야하는 경우
// 0 0 1 0 0 -> seq = [0, 0, 1, 0, 0]

seq = list(map(int, sys.stdin.readline().split()))

itertools 의 combinations (조합)

• 확률과 통계에 등장하는 그 친구
• itertools 패키지에 얌전히 잘 구현되어 있음

from itertools import combinations

iter_seq = list(combination(m, n))

// list로 감싸야지 배열의 형태로 받을 수 있음
// m 에서 n을 선택할 때의 가능한 조합을 return
// m 에는 list

논리구조

• input의 이중 배열을 순회하며 집과 치킨집에 해당하는 위치 인덱스를 각각 (house_arr, chicken_arr)에 저장
• 가능한 치킨집 m개의 조합을 combination 메서드를 활용해 iter_seq에 list 형태로 저장
• 치킨 거리(집 ~ 치킨집)를 계산해주는 함수 calcu_dist 선언
• 3중 for문의 형태
  1. iter_seq의 순회 (치킨집 조합의 경우의 수 하나씩)
  2. new_chickien_arr에 가능한 조합의 위치 인덱스 저장
  3. house_arr 순회 (집 하나씩 돌아보며 치킨 거리 계산)
  4. house와 new_chicken_arr의 거리를 계산해 min_arr에 추가
  5. 집별 치킨집 순회가 끝나면 min_arr의 최소값(치킨 거리)을 result_arr에 추가
     • 각 치킨집 조합별 모든 집의 치킨 거리가 result_arr에 담기게됨
  6. result_arr의 합이 치킨집 조합별 '전체 도치 치킨 거리' 이므로 answer_arr에는 result_arr의 총합을 담음
• anwer_arr의 최솟값 반환

Python Code

import sys
from itertools import combinations

n, m = map(int, sys.stdin.readline().split())
# sys 모듈 기억 잘 안나서 테스트
# seq = list(map(int, sys.stdin.readline().split()))

chicken_arr = []
house_arr = []

for i in range(n):
    seq = list(map(int, sys.stdin.readline().split()))
    for j in range(len(seq)):
        if seq[j] == 1:
            house_arr.append([i, j])
        elif seq[j] == 2:
            chicken_arr.append([i, j])
        else:
            continue

iter_seq = list(combinations(range(len(chicken_arr)), m))
result = 1000000000
# result 값은 일부러 극단적인 큰 값 제시


def calcu_dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


answer_arr = []

for s in iter_seq:
    new_chicken_arr = [chicken_arr[i] for i in s]
    result_arr = []
    for house in house_arr:
        min_arr = []
        for chiken in new_chicken_arr:
            min_arr.append(calcu_dist(house, chiken))
        result_arr.append(min(min_arr))
    answer_arr.append(sum(result_arr))

print(min(answer_arr))