[#15686] 치킨 배달

RookieAND·2022년 6월 2일

백준 브루트포스 코테

BaekJoon

목록 보기

10/42

❓ Question

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

📖 Before Start

간만에 풀어보는 브루트 포스 알고리즘과 순열 응용 문제다.

이번 문제는 순수하게 완전 탐색 을 통해 원하는 값을 도출해야 하는 문제였다.
브루트 포스와 구현 문제는 오랜만이라 문제를 푸는 과정에서도 제법 재미가 있었다.

✒️ Design Algorithm

치킨 거리 는 각 집마다 가장 가까운 치킨집 간의 거리를 의미한다.

N * N 이차원 배열 내에서, 0 은 빈 공간을 의미하고, 1 은 집, 2 는 치킨집을 의미한다.
집 A(x1, y1) 와 치킨집 B(x2, y2) 사이의 거리는 |x1 - x2| + |y1 - y2| 로 구한다.

모든 치킨집을 대상으로 거리를 구했을 때, 그 중 최솟값을 집 A 의 치킨 거리라 하고,
도시 전체의 치킨 거리는 각 집 간의 치킨 거리를 모두 합한 값 과 같다고 한다.

이차원 배열에 놓인 치킨집 중에서, M 개의 치킨집을 남기고 나머지를 전부 없앴을 때,
도시 전체의 치킨 거리의 최솟값 을 구하면 되는, 비교적 심플한 구현 문제였다.

M개의 치킨집 을 조합으로 추출한 후에, 각 집 간의 치킨 거리를 구해보자!

입력 받은 이차원 배열 중에서, 집인 1 이 든 좌표 (X, Y) 를 별도의 리스트에 저장한다.
입력 받은 이차원 배열 중에서, 치킨집인 2 가 든 좌표 (X, Y) 를 별도의 리스트에 저장한다.
그 후, 조합 (Collections) 을 사용하여 치킨집의 좌표들 중 M 개를 추출하여 List에 저장한다.
해당 치킨집들에 대해서 각 집들 간의 치킨 거리 를 구하고, 이를 모두 합산하여 총합을 구한다.
기존에 저장되었던 도시 전체의 치킨 거리 와 새로이 구한 값을 대조한다.

💻 Making Own Code

✅ Correct Code

import sys
from math import inf
from itertools import combinations as comb

read = sys.stdin.readline
N, M = map(int, read().split())
house_list, chicken_list = [], []

# 일반 가정집과 치킨 집의 목록을 별도로 추출하기 위한 파트
for i in range(N):
    row_list = list(map(int, read().split()))
    for j in range(N):
        if row_list[j] == 1:
            house_list.append((i, j))
            continue
        if row_list[j] == 2:
            chicken_list.append((i, j))

result = inf
# 각 치킨 집의 목록 중에서, M개를 무작위하게 추출함.
for chicken_locs in comb(chicken_list, M):
    min_length = 0
    # 각 집을 순회하며 치킨집 별 치킨 거리를 계산함.
    for house_loc in house_list:
        chicken_len = inf
        # M개로 추출된 치킨집 중에서, 가장 적은 값의 치킨 거리를 찾는 과정
        for chicken_loc in chicken_locs:
            between_len = abs(house_loc[0] - chicken_loc[0]) + abs(house_loc[1] - chicken_loc[1])
            chicken_len = min(chicken_len, between_len)
        min_length += chicken_len
    # 합산하여 나온 도시의 치킨 거리가, 기존의 값보다 작은지 대조
    result = min(result, min_length)
    
print(result)

이 문제는 itertools 라이브러리의 조합 (Collections) 을 사용한다면 비교적 쉽게 풀이가 가능하다.
결국 전체 치킨집들 중 M 개의 치킨집을 산출해서, 도시 전체의 치킨 거리 를 구해야 하는 것이므로,
M 개의 치킨집이 선정되었다면, 그 이후로는 이중 반복문을 통해 결과를 쉽게 구할 수 있다.