[백준] 15686 치킨배달 [시간초과 + 해설 + 코드]

구현

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

15686번: 치킨 배달

 

코드 (AC판정 코드 1552ms)

import sys 
from itertools import combinations
input = sys.stdin.readline

n, m = map(int, input().split())

board=[input().split() for _ in range(n)]
ch = []
home = []
for i in range(n):
	for j in range(n):
		if board[i][j] == "2":
			ch.append([i, j])
		elif board[i][j] == "1":
			home.append([i, j])

t = []
while m > 0:
	for i in combinations(ch, m):
		
		a = []
		for j in home:
			stand = 100
			for c in i:
				dist = min(stand, abs(j[0]-c[0]) + abs(j[1]-c[1]))
				stand = dist
			a.append(stand)
		if a:
			t.append(sum(a))
	m-=1
print(min(t))

 

코드(시간초과)

import sys
from itertools import combinations
input = sys.stdin.readline

n, m = map(int, input().split())
c_c = {}
h_d ={}

city = [input().split() for _ in range(n)]

index = 1
for i in range(n):
	for j in range(n):
		if city[i][j] == "2":
			c_c[index] = [i, j]
			index += 1

for i in range(n):
	for j in range(n): 
		if city[i][j] == "1":
			for k, v in c_c.items():

				dist = abs(i-v[0]) + abs(j-v[1])

				if str(i)+str(j) not in h_d:
					h_d[str(i)+str(j)] = [[k, dist]]
				else:
					h_d[str(i)+str(j)].append([k, dist])


num = set()
for k, v in h_d.items():
	h_d[k] = sorted(v, key=lambda x : x[1])
	num.add(h_d[k][0][0])

total = []
while m > 0:
	for idx in combinations(num, m):
		re = list(idx)
		for j in range(len(re)):

			t = 0
			for k, v in h_d.items():
				c = v
				x = []
				for k in c:
					if k[0] in re:
						x.append(k[1])
				t += min(x)

			total.append(t)

	m -=1

print(min(total))

 

설명

 문제요점만 간단하게 정리해 보자면 해당 문제에서 구하고자 하는 목표는 아래와 같다.

 

 

'치킨집 중에서 최대 M개를 골랐을 때,

어떻게 고르면 도시의 치킨거리가 가장 작게 될지 그때의 거리의 최솟값을 구하여라.'

 

 

 우선 '시간초과'를 받은 코드 부터 왜 시간초과를 받았고 왜 저런 생각을 했는지 간략하게 정리해 보고 정답을 받은 코드와 어떤 발상 차이가 있었는지를 설명해 보고자 한다.

처음 구현하고자 했던 방향은 '치킨집', '집'을 따로 테이블을 만들어서 치킨집의 좌표를 우선적으로 찾아서 하나의 테이블에 넣어놓고, 집을 탐색할 때는 해당 치킨집들의 방향을 그대로 가져와서 거리를 구할 생각을 했었다. 이렇게 한다면 모든 치킨집을 다시 탐색하지 않아도 치킨집의 위치는 좌표계에서 변하지 않기 때문에 고정적인 값들을 빠르게 접근할 수 있게 된다. 그러면 집에 대한 '모든 치킨집 사이의 거리'를 구하고 '집' 테이블에 거리와 어떤 좌표에서 이 값이 계산되었는지를 값으로 가지게 했다. 이렇게 하면 모든 집들은 모든 치킨집들과의 거리를 가지고 있다. 이후에 치킨 거리의 개념을 보자면 "집과 치킨집 사이의 거리가 가장 가까운"이라고 정의가 되어있다. 그렇다는 건 해당 거리들 중 가장 짧은 거리를 가지고 있는 것이 곧 치킨 거리가 된다라고 이해할 수 있다. 이러한 치킨 거리들의 합은 도시의 치킨거리가 된다.

왜냐하면 치킨거리는 가장 짧은 거리이고 도시의 치킨거리는 '치킨 거리의 합'이 되기 때문이다. 결국 가장 짧은 거리의 합이 도시의 치킨거리가 된다.

 

 여기까지는 무난하게 생각을 했다고 생각했다. 이어서 보자면 치킨집 중에서 최대 M개를 선택한다고 했다. 결국 이 말은 최대 M 개니까 무조건 M개라는 뜻이 아니다. M은 1부터 시작하기 때문에 골라야 하는 치킨집의 개수는 1개부터 그리고 13개 이하까지 선택이 가능하다는 말이 된다. 그렇다는 건 개수가 확연하게 작은 걸 보고 '치킨집들 중에서 뽑아야 되니까' 해당 거리를 미리 구해놨던걸 가지고 와서 1~M개까지 '가장 거리가 작은 치킨집들만 가지고 와서 뽑게 되었다.' 그랬을 때 이 거리가 가장 짧은 구간의 좌표에 해당한다면 그중 가장 작은 값들이 답이 되기 때문에 선택된 모든 가장 짧은 거리들의 합을 구하면 도시의 거리가 출력된다.

 

 그럼 이제 AC를 받은 코드와 어떤 차이점이 있는지 살펴보자면 가장 큰 차이는 '처음부터 거리를 모두 구하지 않았다.' 다시 생각해 보니까 문제의 요점은 치킨집 중에서 최대 M개를 골랐을 때 도시의 치킨거리가 가장 작은 걸 원하고 있다. 그렇다는 건 치킨집들을 1~M개 뽑았을 때, 그때의 '뽑힌 치킨집' 들과 거리를 구해주면 '각 집당 뽑힌 치킨집들과의 거리 중 가장 짧은 걸' 뽑힌걸 기준으로 바로 구할 수 있다. 시간초과를 받은 코드에서는 모든 거리를 다 구해놓고 거리가 짧은 것들 중에서 뽑힌 치킨집이 있을 때 그 좌표에 해당하는 값들 중 작은 값을 계산하고 있다. 결국 모든 거리를 구한걸 다시 탐색해야 되는 방식이 된다.. 심지어 잘못된 코드에서는 불필요한 정렬을 수행하고 있다. 왜 저렇게 했었냐면 가장 짧은 거리를 구하고자 딕셔너리 값들을 가장 작은 거리의 값을 기준으로 정렬을 한 뒤 가장 짧은 거리를 갖는 좌표들만 얻기 위해서였다. 이는 사실할 이유가 없다. 가장 짧은걸 밑에서도 구하고 있는데 이렇게 되면 결국 '짧은 거리를 구하고 뽑혀진 짧은 거리들을 다시 M개를 뽑은 다음 거기에 포함되어 있는 모든 값들 중 작은 값을 구하고 있다.' 정답 코드와 의도는 동일하다 치킨집을 M개를 뽑았을 때 도시의 치킨거리를 최소로 만들기 위해서 모든 거리들의 짧은 거리의 합이 도시의 거리를 만든다는 의도는 동일하나, 중복된 코드도 있고 결정적으로 combination을 구하는 부분에서 AC를 받은 코드는 치킨집들을 선택하고 그 선택된 치킨집들과의 가장 짧은 거리를 구하고 있다면, 시간초과를 받은 코드에서는 미리 거리를 다 구해두고 가장 짧은 거리의 치킨집들만 선정해서 다시 그 짧은 거리의 포함된 거리들을 합산하고 있다. 시간초과를 받은 코드가 예제 케이스는 다 맞을지 모르나 다른 반례까지 맞는지는 잘 모르겠다.