[이.취.코] [백준] Chap 12. 구현 - Q13. 치킨 배달

@mildsalmon·2021-09-18 06:39

1. 치킨 배달

난이도
- 중
- 골드 5
풀이 시간
- 40분
시간 제한
- 1초
메모리 제한
- 512 MB
출처
- 15686번: 치킨 배달 (acmicpc.net)

A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 내 답안

a. 1차 시도 (성공 / 불필요한 부분이 포함됨.)


from itertools import combinations  
  
n, m = list(map(int, input().split()))  
  
# graph = [[0] * (n+1) for _ in range(n+1)]  
  
city_chicken_distance = 1e9  
graph = []  
  
for i in range(n):  
    graph.append(list(map(int, input().split())))  
  
# for i in range(1, m+1):  
home = []  
chicken = []  
ch_dp = []  
  
# 치킨집과 가정집 각각 리스트에 좌표 추출  
for j in range(n):  
    for k in range(n):  
        if graph[j][k] == 1:  
            home.append([j, k])  
            ch_dp.append(1e9)  
        elif graph[j][k] == 2:  
            chicken.append([j, k])  
  
# 1~m개 치킨집의 조합을 구하기.  
choice = []  
for i in range(1, m+1):  
    a = list(combinations(chicken, i))  
    for j in a:  
        choice.append(j)  
  
# for step in range(1, m+1):  
#     for i in range(0, len(chicken)):  
#         if (i+step) >  
#         choice = chicken[:(i+step)%(len(chicken)+1)]  
  
# 조합된 치킨집과 가정집 사이의 멘헤튼 거리를 측정하고 최솟값을 찾는다.  
for i in choice:  
    ch_dp_t = ch_dp[:]  
  
    for j in range(len(home)):  
        for k in i:  
            ch_dp_t[j] = min(ch_dp_t[j], abs(home[j][0] - k[0]) + abs(home[j][1] - k[1]))  
    city_chicken_distance = min(city_chicken_distance, sum(ch_dp_t))  
  
print(city_chicken_distance)  
  
# 48분 / pass / 치킨집을 조합안쓰고 하나씩 고르려다가 시간초과...

조합을 전 범위를 다 지정하여 필요없는 연산 시간이 증가하는 문제가 있음.

b. 2차 시도 (성공 / 위 문제 해결 및 가독성 있게 주석 추가)


# 치킨 배달

from itertools import combinations

N, M = list(map(int, input().split()))
array = []
houses = []
chickens = []

for i in range(N):
    temp = list(map(int, input().split()))

    array.append(temp)
    for j in range(len(temp)):
        if temp[j] == 1:
            houses.append((i, j))
        elif temp[j] == 2:
            chickens.append((i, j))

combination_chickens = combinations(chickens, M)

min_town_chicken_distance = 1e9
# 치킨집 조합에서 하나를 선택
for chickens in combination_chickens:
    town_chicken_distance = 0
    # 집들 중 하나 선택
    # 각 집과 조합에서 선택된 치킨집 사이의 가장 가까운 치킨 거리 계산
    for house in houses:
        min_chicken_distance = 1e9
        for chicken in chickens:
            chicken_distance = abs(house[0] - chicken[0]) + abs(house[1] - chicken[1])
            min_chicken_distance = min(min_chicken_distance, chicken_distance)
        # 구한 치킨 거리를 도시의 치킨 거리에 더함.
        town_chicken_distance += min_chicken_distance
    min_town_chicken_distance = min(min_town_chicken_distance, town_chicken_distance)

print(min_town_chicken_distance)

시간 단축 !

c. 회고

내 풀이

도시 정보를 game_map 저장하듯 저장한다.
- 치킨집과 가정집을 따로 리스트에 추출한다.
- 치킨집과 가정집 사이의 거리를 구해야 한다. 치킨집의 수는 변하지만 가정집의 수는 변하지 않는다. 따라서 가정집의 수만큼 무한대의 값을 가지는 리스트를 만든다.
치킨집을 선택해야한다.
- 치킨집 조합을 직접 짜주려다가 시간을 많이 낭비했다.
- 결국에는 combinations으로 풀었다.
치킨집 조합과 집 사이의 맨해튼 거리를 측정한다.
- 치킨집 조합에서 치킨집 리스트를 하나 뽑고 각각의 집에서 치킨집 사이의 최솟값을 구한다.
- 이러면 해당 치킨집 조합에서 가장 짧은 치킨 거리를 구할 수 있다.
- 이 거리들의 합이 치킨집을 M개 폐업시키지 않았을때의 최솟값을 갖는 도시의 치킨거리이다.
- 이들 중에 최솟값을 찾으면 된다.