[python]백준 15686번: 치킨 배달(브루트포스)

# 15686 치킨 배달

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

15686번: 치킨 배달

코드

from itertools import combinations
N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

house = [] # 집 좌표
chicken = [] # 치킨집 좌표

for r in range(N): # x
  for c in range(N): # y
    if graph[r][c] == 1: house.append([r,c]) # [[0, 2], [1, 4], [2, 1], [3, 2]]
    elif graph[r][c] == 2: chicken.append([r,c]) # [[1, 2], [2, 2], [4, 4]]

result = 1e9 # 1000000000.0
for x in combinations(chicken, M): # 치킨집 좌표 리스트를 기준으로 M개 조합 ([1, 2], [2, 2], [4, 4])
  graph_dist = 0
  for h in house: # 전체 집 순회
    house_dist = 1e9
    for k in x: # 집별로 치킨집 순회
      house_dist = min(house_dist, abs(h[0]-k[0]) + abs(h[1]-k[1])) # 집별로 가장 가까운 치킨집 거리
    graph_dist += house_dist # 도시 치킨 거리 += 집에서 가장 가까운 치킨집 거리
  result = min(result, graph_dist)

print(result)

📝 풀이

치킨집과 일반집과의 거리를 계산해야하며 주어진 M으로 치킨거리 최단거리를 만들어야 이윤이 크다는 시나리오로 보인다. 그렇기 때문에 M개의 치킨 집 조합(combination)을 구해서 집마다 치킨 집까지의 최소 거리를 계산하고 모든 조합에 대해 과정을 반복하면서 치킨 거리 합의 최솟값을 계산하면 된다.

graph = [list(map(int, input().split())) for _ in range(N)]

house = [] # 집 좌표
chicken = [] # 치킨집 좌표

for r in range(N): # x
  for c in range(N): # y
    if graph[r][c] == 1: house.append([r,c]) # [[0, 2], [1, 4], [2, 1], [3, 2]]
    elif graph[r][c] == 2: chicken.append([r,c]) # [[1, 2], [2, 2], [4, 4]]

이중 반복문을 사용해서 주어진 범위를 모두 탐색해 1인 집과 2인 치킨집을 각각의 리스트에 넣어준다. 백준 예제에 따르면 house 리스트에는 [[0, 2], [1, 4], [2, 1], [3, 2]], chicken 리스트에는 [[1, 2], [2, 2], [4, 4]]가 담기게 된다.

result = 1e9 # 1000000000.0
for x in combinations(chicken, M): # 치킨집 좌표 리스트를 기준으로 M개 조합 ([1, 2], [2, 2], [4, 4])
  graph_dist = 0
  for h in house: # 전체 집 순회
    house_dist = 1e9
    for k in x: # 집별로 치킨집 순회
      house_dist = min(house_dist, abs(h[0]-k[0]) + abs(h[1]-k[1])) # 집별로 가장 가까운 치킨집 거리
    graph_dist += house_dist # 도시 치킨 거리 += 집에서 가장 가까운 치킨집 거리
  result = min(result, graph_dist)

print(result)

최솟값을 구하는 것이기 때문에 result에 10억을 넣어주고 chicken리스트의 M개 조합을 순회시켜준다.

house와 조합 x를 순회하면서 house_dist와 집, 치킨집 거리 각각의 절댓값을 더해준 것을 비교해 min값을 house_dist에 저장해준다.

최종적으로 result값과 도시 치킨거리 값을 비교해 min값을 출력해준다.