[백준] 15686 치킨 배달

---

도시에 존재하는 치킨 집을 M개 만큼 남기는 경우의 수 중 최소 치킨 거리를 구하는 문제이다. 

 

모든 치킨 집 중 M개를 뽑는 조합을 구하면 쉽게 답이 도출된다.

 

다만 나는 시간 초과로 인해 조금 헤매었다. 그 이유는 지금까지 조합과 순열에 대한 차이를 인지하면서 알고리즘을 작성하지 않았던기 때문이다. 

 

조합은 순서를 무시하기 때문에 [1, 2]와 [2, 1] 동일하다. 즉 [(1, 2), (3, 2)]에 위치한 치킨 집을 폐업 시키는 경우와 [(3, 2), (1, 2)]에 위치한 치킨 집을 폐업 시키는 경우가 동일한 것이다. 이러한 문제에 순열 알고리즘을 사용하였으니 시간초과가 발생하는 것이 당연한 것이었다.

순열과 조합 알고리즘의 간단한 예시는 아래와 같다.

# 순열

li = [1, 2, 3, 4, 5, 6]
M = 4

def dfs(result):
    if len(result) == M:
        return
    print(result)
    for l in li:
        dfs(result + [l])
dfs([])

# 조합

li = [1, 2, 3, 4, 5, 6]
M = 4

def dfs(idx, result):
    if idx >= len(li): return
    if len(result) == M:
        return
    print(result)
    dfs(idx+1, result + [li[idx]])
    dfs(idx+1, result)

dfs(0, [])

 

Python

 

	from sys import stdin
	readline = stdin.readline
	N, M = map(int, readline().split())
	home = []
	chicken = []
	result = []
	ans = 2 * N**2
	for r in range(N):
	line = list(map(int, readline().split()))
	for c in range(N):
	if line[c] == 1:
	home.append((r, c))
	elif line[c] == 2:
	chicken.append((r, c))
	def solve(idx, cnt):
	global ans
	if idx > len(chicken): return
	if cnt == M:
	t = 0
	for hr, hc in home:
	dist = 2 * N + 1
	for j in result:
	cr, cc = chicken[j]
	dist = min(dist, abs(hr-cr) + abs(hc-cc))
	t += dist
	ans = min(ans, t)
	return
	result.append(idx)
	solve(idx+1, cnt+1)
	result.pop()
	solve(idx+1, cnt)
	solve(0, 0)
	print(ans)

view raw BOJ15686.py hosted with ❤ by GitHub