모든 도시를 한 번씩 들러 출발점으로 돌아오는 최소 비용 경로를 찾는 문제다. 완전탐색이면 (n-1)! 이다.
얼마나 큰지 세어보기
먼저 크기를 몸으로 확인해보려고 했다.
def fec(n):
if n == 1:
return 1
return n * fec(n - 1)
n = 20
t = fec(n)
cnt = 0
for i in range(t):
cnt += 1
print(cnt)
20!만큼 반복문을 돌린다. 20!은 2432902008176640000이다. 1초에 1억 번을 돈다고 해도 770년쯤 걸린다.
당연히 끝나지 않는다. 숫자로 보는 것과 반복문을 실제로 돌려보는 건 다르다는 걸 확인하려던 파일로 보인다.
남은 도시를 집합으로 넘기기
def rec(path, left, cost):
if len(left) == 0:
print(path, cost)
return
cur = path[-1]
for i in left:
for j in dict[(cur, i)]:
rec(path + j[0], left - set(j[0]), cost + j[1])
path = [0]
left = set(range(1, n))
지금까지의 경로, 남은 도시 집합, 누적 비용 세 개를 들고 다닌다. left 가 비면 다 돈 것이다.
방문 여부를 path 에서 찾지 않고 집합으로 따로 둔 게 낫다. in 으로 확인할 때 리스트는 처음부터 훑지만 집합은 그렇지 않다.
부분 경로를 재사용하려던 생각
그냥 완전탐색으로는 답이 없으니 중간 경로를 저장해서 다시 쓰려고 했다. 같은 폴더의 notebook에 그 구상이 적혀 있다.
두 끝 대각선을 정해놓고, 그 사이에 가능한 것들을 고려하면 됨. 2개까지는 문제에서 주어주니, 3개 이상의 길이에 대한 것들을 모두 기록하면 됨.
{(1,3): [[1,2,3, 5], [1,4,2,5,6,3, 100]]}
시작점과 끝점의 쌍을 키로 두고, 그 사이를 잇는 경로들과 각각의 비용을 담아둔다는 것이다. (1, 3) 을 지나는 더 긴 경로를 만들 때 여기 있는 걸 꺼내 쓴다.
코드에는 주석으로 남아 있다.
# le = path[-2] # last end <- 첫번째에는 이게 없음. 이거 해결 필요 !!!!
# for i in range(len(path) - 2):
# s = path[i] # start point
# p = path[i:] # path
# c = dict[(s, le)][-1][1] + dict[(le, cur)][0][1]
# dict[(s, cur)].append(p, c)
막힌 지점이 주석에 그대로 적혀 있다. 지금 경로를 늘릴 때 직전 끝점 path[-2] 가 필요한데, 경로가 하나뿐인 첫 단계에는 그게 없다.
완성하지 못했다
dict 를 만드는 부분도 어긋나 있다.
dict[(i, j)] = [[j], k[j]]
두 칸짜리 리스트다. 첫 칸은 경로 [j] 이고 둘째 칸은 비용이다. 그런데 쓰는 쪽에서는 이렇게 한다.
for j in dict[(cur, i)]:
rec(path + j[0], left - set(j[0]), cost + j[1])
dict[(cur, i)] 를 경로 목록으로 보고 훑는다. 실제로는 [경로, 비용] 한 쌍이라 j 에 경로와 비용이 차례로 들어온다. 담아둔 모양과 꺼내 쓰는 모양이 맞지 않는다.
같은 키에 여러 경로를 쌓을 생각이었으니 dict[(i, j)] = [[[j], k[j]]] 처럼 한 겹 더 있어야 했다. 저장 구조를 정하기 전에 쓰는 쪽을 먼저 써버린 것으로 보인다.
notebook 쪽 셀은 for 아래가 비어 있는 채로 남아 있다.