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

  • 0
  • 0
0
0

1. 치킨 배달

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개 폐업시키지 않았을때의 최솟값을 갖는 도시의 치킨거리이다.
    • 이들 중에 최솟값을 찾으면 된다.

반성

  • 굳이 도시 정보를 전부 저장할 필요는 없었다. 맨해튼 거리를 구하기 위해서는 두 좌표만 알면 되기 때문이다.

결론

  • 맨해튼 거리를 봤다면, map을 저장하지 말고 해보자

C. 문제 해설

이해한 내용을 바탕으로 작성했습니다.

a. 책 답안

python-for-coding-test/7.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] 15686번: 치킨 배달 (acmicpc.net). Baekjoon. (accessed Sep 18, 2021)

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.