[백준/Python] 15656번 - 치킨 배달

문제

백준 15656번 - 치킨 배달

조합 해결 과정

• chicken: 치킨 집 위치를 담은 리스트
  house: 집의 위치를 담은 리스트
• 치킨 집들 중에서 m개를 뽑아 조합으로 만든다.
  • chicken_total_dist: 각 집에서 가장 가까운 치킨 집의 거리를 모두 더한 값
    -> 0으로 초기화
  • 각 집에서 가장 가까운 치킨 집의 거리 구하기
    • chicken_dist: 집에서 가장 가까운 치킨 거리
      -> 가장 큰 값으로 초기화
    • 해당 집이랑 모든 치킨 집의 거리를 확인하며 둘 중 작은 값을 chicken_dist로 갱신
  • 해당 집과 가장 가까운 거리의 치킨 집을 담고있는 chicken_dist를 chicken_total_dist에 더하기
  • chicken_total_dist를 ans와 비교하며 가장 작은 값 넣기

백트래킹 해결 과정

• 0번 치킨 집부터 하나씩 select에 넣다가 선택된 치킨 집의 개수가 m개 일 때 거리를 계산하며 모든 경우의 수를 계산한다.

시행착오

• 백트래킹으로 푸는거 모르겠음.. 찾아보니 combination으로 풀었길래 다시 풀어본다.

조합 풀이

import sys
from itertools import combinations

n,m = map(int,sys.stdin.readline().split())

map = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]

# 모든 집의 치킨 거리의 합 = 도시의 치킨 거리 -> 최소값을 구하기
ans  = int(1e9)

# 도시의 치킨 거리 최소값 구하기
def solve():
  global ans
  # 남겨둘 치킨 집의 조합
  for c in combinations(chicken,m):
    # 각 집에서의 치킨 거리를 합한 것
    chicken_total_dist = 0
    # 각 집에서의 치킨 거리
    for h in house:
      chicken_dist = int(1e9)
      # 집 하나랑 모든 치킨 집의 거리를 구해서 가장 작은 값을 구한다.
      for i in range(m):
        chicken_dist = min(chicken_dist, abs(h[0] - c[i][0]) + abs(h[1] - c[i][1]))
      chicken_total_dist += chicken_dist
    ans = min(chicken_total_dist,ans)

chicken = []
house = []

for i in range(n):
  for j in range(n):
    if map[i][j] == 1:
      house.append([i,j])
    elif map[i][j] == 2:
      chicken.append([i,j])

solve()
print(ans)

백트래킹 풀이

import sys

n, m = map(int, sys.stdin.readline().split())                      
map = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]


# depth: 고른 치킨집 수, i: 고른 치킨집 번호
def back(depth, i):      
  global result
  chicken_total_dist = 0
  # 치킨집 m개를 골랐다면 치킨 거리 계산
  if depth == m:
    for h in house:
      chicken_dist = int(1e9)
      for c in select:
        chicken_dist = min(chicken_dist, abs(h[0]-c[0]) + abs(h[1]-c[1]))
      chicken_total_dist += chicken_dist
    result = min(chicken_total_dist,result)
    return
	# 고른 치킨 집을 제외하고 back
  for idx in range(i, K):
    select.append(chicken[idx])
    back(depth+1, idx+1)
    select.pop()

chicken = []
house = []

select = []
for i in range(n):
    for j in range(n):
        if map[i][j] == 1:        
            house.append((i, j))
        elif map[i][j] == 2:      
            chicken.append((i, j))

K = len(chicken)      # 총 치킨집 수
result = int(1e9)     

# 조합 시작
for t in range(K):
  back(0, t)

print(result)