1. 문제
  2. 접근
    1. 그리디 알고리즘을 사용하면 안되는 이유
    2. 완전탐색 시간복잡도 계산
    3. Itertools combinations() 함수 이용
  3. 풀이

문제

BOJ 15686번 치킨 배달

접근

  • 집 하나의 치킨거리를 구하기 위해 처음에는 BFS를 이용하여, 해당 집(1)에서 출발해 가장 가까운 직선거리에 있는 치킨집(2)을 발견하면 그 거리를 구했다. 결과는 당연히 시간초과. 치킨집들의 좌표를 배열로 저장해두고 각각으로의 치킨거리를 계산해서 최소값을 찾는 게 훨씬 빠르다.

  • itertools를 몰라서 치킨 가게들 중 m개를 임의로 선택하는 함수를 직접 백트래킹으로 구현했었다. 알고리즘은 동일했겠지만 시간초과가 나왔다.

그리디 알고리즘을 사용하면 안되는 이유

도시의 치킨거리를 가장 많이 줄여주는 치킨집부터 m개를 고르는 방법도 생각해보았지만, 이 문제는 그리디 알고리즘을 사용하면 안된다. m에 따라 고르는 치킨집의 조합이 전혀 달라질 수 있기 때문이다.

완전탐색 시간복잡도 계산

치킨집의 최대 개수는 13, 집의 최대 개수는 2N = 100개이다. 치킨집의 조합의 가짓수가 가장 많으려면 m=6일때, 13C6으로 약 1700이다. 그럼 이 조합마다 도시의 치킨거리를 계산하는데 100*13=1300의 계산이 필요하다고 해도 1700*1300 < 10^8로 주어진 1초 내에 해결 가능하다.
컴퓨터는 1초에 약 1억번의 연산이 가능한 것을 이용해, 문제를 풀기 전 복잡도를 구해서 가능한 알고리즘인지 확인해보는 습관을 들여야겠다.

Itertools combinations() 함수 이용

Python 내장 모듈 Itertools내에 주어진 집합의 부분집합을 반환해주는 함수 combinations()가 있다는 걸 알게되었다. 이를 이용하면 굳이 백트래킹으로 조합을 일일히 반환하지 않아도 된다.

  • permutations(p,r): p의 부분집합 중 중복된 원소 없이 길이가 r인 부분집합의 배열을 반환
  • combinations(p,r) : p의 부분집합 중 중복된 원소 없이 길이가 r이고 사전순으로 정렬된 부분집합의 배열을 반환
  • combinations_with_replactment(p,r) : p의 부분집합 중 원소의 중복을 허용하는 길이가 r이고 사전순으로 정렬된 부분집합의 배열을 반환

풀이

BOJ 15686 치킨 배달
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import sys
from itertools import combinations
input = sys.stdin.readline

n,m = map(int, input().split())
home = []
store =[]

for x in range(n):
  row = list(map(int,input().split()))
  for y in range(n):
    if row[y] == 2:
      store.append([x,y])
    elif row[y] == 1:
      home.append([x,y])

def nearest(i,j):
  d = 999999
  for [x,y] in selected:
    d = min(d, abs(i-x)+abs(j-y))
  return d

def chicken():
  chicken = 0
  for [x,y] in home:
    chicken += nearest(x,y)
  return chicken

min_chicken = 999999
for selected in combinations(store, m):
  min_chicken = min(min_chicken, chicken())
print(min_chicken)

참고자료
itertools 공식 문서