[Solved] BOJ: 15686 | 치킨거리

문제

N * N 의 2차원 배열로 이루어진 도시 정보를 입력받는다.
0은 빈 칸, 1은 집, 2는 치킨집
주어진 치킨집들 중에서 도시 전체의 치킨 거리가 최소가 되게 하는 M개의 치킨집을 채택하여
그 최소가 되는 도시 전체의 치킨 거리를 구해보자

• 도시 전체의 치킨 거리는 각각의 집들의 치킨 거리 총합
• 각각의 집들의 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리

입력과 출력

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.
도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

---

문제 해결 요약

M개의 치킨집 조합에 대한 치킨 거리를 모두 구해 -> 브루트포스
그 중 최솟값을 출력한다

코드 설명

import 및 입력받기

도시의 정보를 입력받는다.

-

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

n, m = map(int, input().split())
city = []
house = []
chicken = []
for i in range(n):
    tmp = list(map(int, input().split()))
    city.append(tmp)
    for j in range(len(tmp)):
        if tmp[j] == 1:
            house.append((i, j))
        elif tmp[j] == 2:
            chicken.append((i, j))

• city에는 도시의 전체 정보
• house에는 집 좌표
• chicken에는 치킨집 좌표를 저장한다

치킨집 조합에 대한 치킨 거리 계산

치킨집 조합에 대한 집들의 개별 치킨 거리를 계산하여 도시 전체의 치킨 거리를 구한다.

-

chicken_dist = 2*(n-1)*len(house) # 최대 치킨 거리 * 집 개수
for combi in combinations(chicken, m):
    total_dist = 0
    for h in house:
        one_dist = 2*(n-1) # 최대 치킨 거리
        for c in combi:
            one_dist = min(one_dist, dist(c, h))
        total_dist += one_dist
    chicken_dist = min(chicken_dist, total_dist)

• chicken_dist 도시 전체의 치킨 거리를 최대 치킨 거리 * 집 개수로 초기값을 지정해준다
• 치킨집 조합에 대한 개별 치킨 거리 one_dist 최솟값을 계산하여
• total_dist 에 더해주어 도시 전체의 치킨 거리를 계산한다
• chicken_dist와 total_dist와 비교하여 둘 중 최소값으로 chicken_dist를 갱신한다.

치킨 거리 함수

편의를 위해 치킨 거리 함수를 정의한다.

-

def dist(loc1, loc2):
    return abs(loc1[0]-loc2[0]) + abs(loc1[1]-loc2[1])

---

전체 코드