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

🥚문제

---

🥚입력/출력

---

🍳코드

1번 코드 (시간: 880ms)

import itertools
import sys
input = sys.stdin.readline

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


def get_chicken_dist(r1, c1, r2, c2):
    # 치킨 거리 = 집과 가장 가까운 치킨집 사이의 거리 = |r1-r2| + |c1-c2|
    return abs(r1-r2) + abs(c1-c2)


# 집과 치킨집의 좌표를 추출
home = []
chicken = []
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            home.append((i, j))
            continue
        if city[i][j] == 2:
            chicken.append((i, j))

# m개의 치킨집 조합을 구성
combis = list(itertools.combinations(chicken, m))

ans = 1000000

# 치킨집을 combi 조합으로 남겨놓았을 때, 도시 전체의 치킨거리
for combi in combis:
    # 도시의 치킨 거리 = 모든 집의 치킨 거리의 합
    city_dist = 0
    # 각 집에서의 치킨거리
    for target_home in home:
        tmp_dist = 1000000
        for j in range(m):
            # 가장 가까운 치킨집까지의 거리
            tmp_dist = min(tmp_dist, get_chicken_dist(
                target_home[0], target_home[1], combi[j][0], combi[j][1]))
        # city_dist에 target_home의 치킨거리 더함
        city_dist += tmp_dist

    ans = min(ans, city_dist)

print(ans)

2번 코드 (시간: 536ms)

import itertools
import sys
input = sys.stdin.readline

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

# 치킨 거리 = 집과 가장 가까운 치킨집 사이의 거리 = |r1-r2| + |c1-c2|
def get_chicken_dist(r1, c1, r2, c2):
    return abs(r1-r2) + abs(c1-c2)


# 치킨집과 집의 좌표를 추출
home = []
chicken = []
for i in range(n):
    for j in range(n):
        if city[i][j] == 1:
            home.append((i, j))
            continue
        if city[i][j] == 2:
            chicken.append((i, j))

# 집, 치킨집의 개수
n_home = len(home)
n_chicken = len(chicken)

# chicken_dist[i][y] = 집 i에서 치킨집 y로의 치킨 거리
chicken_dist = [[0]*n_chicken for _ in range(n_home)]
for i in range(n_home):
    for j in range(n_chicken):
        chicken_dist[i][j] = get_chicken_dist(
            home[i][0], home[i][1], chicken[j][0], chicken[j][1])


# 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때
# 도시의 치킨 거리의 최솟값을 출력
if n_chicken == m:
    print(sum(map(min, chicken_dist)))
elif n_chicken > m:
    # 폐업시킬 치킨집 n_chicken - m개의 조합을 구함
    combis = list(itertools.combinations((
        [x for x in range(n_chicken)]), n_chicken-m))

    # 각 조합에 맞추어 폐업시켜보면서 min_dist 갱신
    min_dist = 1000000
    for combi in combis:
        # 조합에 따라 폐업시킨 후의 chicken_dist
        new_chicken_dist = []
        for i in range(n_home):
            tmp_row = []
            for j in range(n_chicken):
                # 조합에 들어있는 치킨집은 폐업 -> new_chicken_dist에 포함시키지 않는다
                if j in combi:
                    continue
                tmp_row.append(chicken_dist[i][j])
            new_chicken_dist.append(tmp_row)
        # min_dist 갱신해
        min_dist = min(min_dist, sum(map(min, new_chicken_dist)))
    # 출력
    print(min_dist)

---

🧂아이디어

구현, 조합

• 치킨집 m개의 조합을 각각 테스트하면서 전체 도시의 치킨거리가 최소인 값을 구한다
• Python의 itertools를 사용하여 유지할 m개의 치킨집의 조합을 구했다

• 1번 코드
  • m개의 치킨집 조합을 구한 뒤 각 조합별 도시의 치킨 거리를 구한다. 결과적으로 최소가 되는 도시의 치킨 거리를 출력한다.
  • min을 이용해 계속 값을 갱신시켜준다
• 2번 코드
  • chicken_dist[i][j]: 집i에서 치킨집j까지의 치킨거리를 리스트에 먼저 저장해 놓는다
  • itertools를 이용해 폐업시킬 치킨집의 조합을 구한 뒤 (유지할 치킨집의 조합을 구해도 똑같음)
  • chicken_dist에서 폐업하는 치킨집의 column을 제외한 new_chikcne_dist를 만든다.
  • new_chicken_dist의 각 row의 최소값을 더한 것이, 그 조합에서 얻을 수 있는 전체 도시 치킨 거리의 최소. 이를 모든 조합에 대해 반복하여 결과적으로 최소가 되는 도시의 치킨 거리를 출력한다.