[Combination] 백준#15686: 치킨 배달/Python 풀이

📝 문제

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

15686번: 치킨 배달

💡 접근법

조합(combination)을 활용하여 문제를 해결하였습니다. 치킨 집의 탐색 순서가 치킨 집과 가정집 간 거리 합의 최솟값에 영향을 주지 않기 때문에, 전체 원소 중 \(N\)개 뽑는 경우의 수를 구해주는 조합을 사용했습니다. 문제 해결절차는 다음과 같이 크게 3단계입니다.

• 1️⃣ \(M\)개의 치킨 집 조합(combination) 구하기
• 2️⃣ 집마다 치킨 집까지의 최소 거리 계산
• 3️⃣ 모든 조합에 대해 2️⃣ 과정을 반복하여 치킨 거리 합의 최솟값 계산

💻 코드

1) 전체 코드

import sys; input = sys.stdin.readline
from itertools import combinations

def solve():
    global answer
    for chicken in combinations(chicken_list, M):
        chicken_dist_total = 0
        for house in house_list:
            chicken_dist = int(1e9)
            for i in range(M):
                chicken_dist = min(chicken_dist, abs(house[0] - chicken[i][0]) + abs(house[1] - chicken[i][1]))
            chicken_dist_total += chicken_dist
        answer = min(answer, chicken_dist_total)
    return

if __name__ == '__main__':
    N, M = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(N)]
    house_list = []
    chicken_list = []
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 1:
                house_list.append((i, j))
            elif graph[i][j] == 2:
                chicken_list.append((i, j))
    answer = int(1e9)
    solve()
    print(answer)

2) 해설

(1) 라이브러리 import

import sys; input = sys.stdin.readline
from itertools import combinations

• sys 모듈
  • 파이썬 내장함수인 input보다 빠르게 값을 입력받기 위해 sys.stdin.readline 사용

• combinations 모듈
  • itertools 패키지에 combinations 모듈은 전체 원소 중 \(N\)개 뽑는 경우의 수를 구해주는 조합(Combination) 지원

(2) main 함수

if __name__ == '__main__':
    N, M = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(N)]
    house_list = []
    chicken_list = []
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 1:
                house_list.append((i, j))
            elif graph[i][j] == 2:
                chicken_list.append((i, j))
    answer = int(1e9)
    solve()
    print(answer)

 탐색 시 좌표를 기준으로 인덱싱하기 위해 치킨집과 가정집의 좌표를 리스트에 저장하였습니다.

(3) 풀이

def solve():
    global answer
    for chicken in combinations(chicken_list, M):
        chicken_dist_total = 0
        for house in house_list:
            chicken_dist = int(1e9)
            for i in range(M):
                chicken_dist = min(chicken_dist, abs(house[0] - chicken[i][0]) + abs(house[1] - chicken[i][1]))
            chicken_dist_total += chicken_dist
        answer = min(answer, chicken_dist_total)
    return

• 3번째 라인: 치킨집 조합 구하기
  • Combination을 활용하여 최대 \(M\)개의 치킨집의 조합 구하기

📝 채점 결과

정답 확인

💾 Github

https://github.com/park-gb/algorithm-problem-solving/blob/main/etc/boj_15686.py

GitHub - park-gb/algorithm-problem-solving: 알고리즘 문제 풀이 및 정리

---

포스팅 내용에 오류가 있거나 접근법 및 코드 관련 피드백 환영합니다!😄
아래에 👇👇👇 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다 :)
고맙습니다.