0. 목차
1. Dynamic Programming (DP)
2. 외판원 순회 문제(TSP)
어제는 일요일이었기에 TIL을 생략하고 8일차 TIL을 업로드한다.
그렇다고 어제도 공부를 하지 않은 것은 아니었는데, 어제부터 시작해 오늘까지 하루종일 괴롭혔던 건 외판원 순회 문제(TSP)였다.
먼저 외판원 순회 문제에 대한 설명을 읽어보자.
1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.
각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.
N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.
외판원 문제는 완전 탐색 문제로, 일반적으로는 Dynamic Programming으로 풀거나 DFS로 푸는 해법이 대다수인 것으로 보인다.
처음에는 슥 읽어보고 순열을 사용해 풀면 되겠다는 생각으로 접근했다.
예제로 주어진 케이스는 N=4였기에, "생각보다 별 거 없는데?"하며 후다닥 풀었다. 코드를 소개하면
#My solution: By using permutations
from sys import stdin
from itertools import permutations
n = int(stdin.readline())
w = []
for i in range(n):
li = list(map(int, stdin.readline().split()))
w.append(li)
citys = []
for i in range(1, n+1):
citys.append(i)
citys_path = list(permutations(citys))
total_path_list = []
for i in citys_path:
i = list(i)
i.append(i[0]) # i에는 총 N+1개 값이 배정(마지막에는 맨 처음 도시)
pay_sum = 0
for j in range(len(i)-1):
from_city = i[j]
to_city = i[j+1]
if w[from_city-1][to_city-1] == 0:
break
else:
pay_sum += w[from_city-1][to_city-1]
total_path_list.append(pay_sum)
print(min(total_path_list))이렇게 풀었더니 마주한 결과는 메모리 초과.
문제는 citys_path 에 있었다.
citys_path = list(permutations(citys))
순열을 list로 받아 저장하는 구조인데, 공간 복잡도가 O(N!)이다 보니 도시 개수의 최대값인 10이 들어오면 10! =3628800이라는 무지막지한 경우의 수를 저장한다. 이때 사용하는 메모리 양을 체크해보니 2.9기가..(메가 아님..)
순열로 푸는 건 여기서는 쓰지 못하겠다 싶어(하지만 뒤에 순열 풀이 역시 소개할 예정. 이 문제에서는 아슬아슬하게 순열을 사용해서 풀 수 있다.) Dynamic Programming과 DFS를 공부했다. 오늘자 TIL에서는 DP를 중점적으로 소개해본다.
1. Dynamic Programming (DP)
DP를 공부할 때 참조한 콘텐츠는 아래와 같다.
- 출처: 코드없는 프로그래밍
Dynamic Programming은 세 가지 충족조건을 만족할 경우에 사용 가능한 방법이다.
- Problem이 더 작은 sub-problem으로 쪼개질 때
- 밑에서 sub를 풀면 위의 problem에 대한 해답을 구할 수 있을 때
- sub-problem이 겹칠 때(이게 중요한데, 앞에서 이미 sub를 풀었다면 뒤에서는 동일한 sub-problem을 풀지 않아도 되기 때문이다. 앞에서 구한 sub-problem에 대한 값을 저장해두었다가 뒤에서 동일한 sub-problem을 만날 때 꺼내는데, 이를 Memoization이라고 한다.)
코드없는 프로그래밍에서는 대표적인 DP 예제로 피보나치 수열을 소개한다. 피보나치 수열의 점화식은 F(n) = F(n-1) + F(n-2)이다. 아래 이미지에서 보다시피
F(n)은 계속해서 쪼개지며
(1: sub-problem으로 쪼개지는가)
아래 피라미드에 있는 값들을 구하면 위의 값을 구할 수 있고
(2: sub-problem의 솔루션으로 더 큰 problem의 솔루션을 구할 수 있나)
F(5)의 경우 F(4)와 F(3)에 대한 값을 구한 뒤 이를 저장하는데, F(6)을 구하려면 F(4)가 필요하고 이는 앞서 저장해두었기에 추가적인 계산 없이 바로 꺼내쓰면 된다.
(3: sub-problem이 겹치나)
DP와 재귀의 차이점
설명과 예제를 보다보니 재귀와 매우 비슷한 느낌이 들었다. 피보나치 역시 재귀 문제가 아니던가? 좀 찾아보니 둘의 차이점이라고 하면
- 재귀는 하향식이라는 점(DP도 상향식 DP가 있고 하향식 DP가 있으나 주로 사용하는 DP는 상향식인 것으로 확인)
- 가장 큰 차이인 Memoization을 하는지의 여부다.
여기서 2번이 굉장히 중요한데, 앞서 구한 값이 뒤에 또 나오기 때문에 미리 저장해두고 해당 값을 만나면 계산 없이 바로 불러오면 되기 때문에 공간 복잡도가 O(1)이기 때문이다.
if 앞서 정답을 저장해둔 array 안에 해당 값이 있으면?
걔를 출력
else 없다면?
그 솔루션의 답을 푼다.
그런데 좀 더 알아보니 둘이 명확하게 구분되는 개념이라기보다 DP는 "문제를 여러 부분 구조로 쪼갠 뒤 여러 번 중복 계산되는 부분을 한 번만 계산하도록 해 연산 속도를 높이는 방법을 칭할 뿐"이라고 한다. 여기서 앞서 푼 결과를 저장하는 방법을 memoization (메모"이"제이션) 이라고 부르고 이를 반복문으로 구현할지 어쩔지는 상황에 따라 다르니 꼭 정답은 없다고 봐야겠다.
상향식(Bottom-up) DP와 하향식(Top-down) DP
피보나치 수열 문제를 하향식으로 풀어보자.
#Top-down DP
fib_arry = [0, 1] # F(0), F(1)에 대응하는 값만 저장해놓기.
def fib_recur_dp(n):
if n < len(fib_arry): # n이 기존 arry에 있다면 기존 arry에서 해당 n을 인덱스로 하는 값(F(n)을 꺼내온다.
return fib_arry[n]
else: #n이 기존 arry에 없으면 새로 계산 해온 뒤, fib_arry에 추가한다.
fib = fib_recur_dp(n-1) + fib_recur_dp(n-2)
fib_arry.append(fib)
return fib
이러면 어떤 문제가 발생할까? 예컨대 F(10000)을 계산해보면, 우리가 마주하게 되는 건 RecursionError이다. 파이썬이 감당 가능한 maximum recursion depth는 대략 1000인데, 재귀를 10000부터 1까지 돌리다보니 recursion stack을 계속 쌓아놔야 하는데 그 depth가 10000개 가량 계속 쌓이기 때문.
쉽게 말해 F(10000)을 구하려는데 fib_arry에는 [0, 1]만 있으니 F(1)에 도달할 때까지 F(9999), F(9998), F(9997), ..., F(2)까지 계속 내려가야 한다. 여기까지 콜 스택이 계속 쌓이기만 하다 한계치를 넘어서면 에러를 반환한다.
이 문제를 해결하기 위해 등장한 것이 Bottom-up 방식의 DP이다. 이름처럼 F(n)을 구한다고 하면 F(n)에서 출발해서 sub로 쪼개는 게 아니라 가장 작은 sub-problem(F(0), F(1), F(2), ...)부터 Bottom-up 방식으로 array를 채워나가는 방식이다. 이렇게 하면 recursie가 아닌 for loop를 통해서 array를 채워나가는 것이 가능해진다.
코드를 보자.
#Bottom-up
def fib_dp(n):
fib_arry = [0, 1] #arry를 미리 만들어둔다.
if n == 0:
return 0 #F(0) = 0
elif n == 1:
return 0 #F(1) = 0
else:
for i in range(2, n+1):
num = fib_arry[i-1] + fib_arry[i-2]
fib_arry.append(num) #i=2부터 i=n까지 F(2)부터 차곡차곡 쌓는다!
return fib_arry[n]이 Bottom-up 방식의 time complexity는 O(n!)이나 space complexity는 O(1)이다. n개의 값이 array에 저장되니까 O(n)이 아냐? 라고 물을 수 있지만 F(2)를 구하려면 F(0), F(1)이 필요하고 F(3)을 구하려면 F(2)와 F(1)만 필요하다. 즉, F(n)을 구할 때 F(n-1), F(n-2)를 제외한 나머지는 삭제하면 그만이다. 굳이 메모리에 들고 있어야 할 필요가 없으니 결과적으로 O(1)이다.
정리하면, DP 문제를 풀기 위한 핵심은 문제가 큰 Problem과 잘게 쪼개지는 sub-problem으로 나누어지며 이를 잘 정의하는 것이다.
2. 외판원 순회 문제(TSP: Traveling Salesman Problem)
다시 본론으로 돌아오자. DP를 공부하게 된 배경은 외판원 문제를 풀기 위해서였다. 여기서는 아래의 유튜브 영상을 참조했다.
출처: 주니온TV
이 문제를 풀기 앞서, 우리가 명심해야 할 개념이 하나 있다. 바로 순환 문제(처음에 출발했던 도시로 다시 돌아오는 경우)라면 첫 시작 도시를 고정해도 된다는 점이다. 위의 영상을 볼 때도 이 개념을 이해해야 왜 V1에서 출발하는 걸 고정으로 하는지를 이해할 수 있다.
처음에 강의에서 말하는 V1, V2, ... 넘버링은 인덱스를 의미하는 건줄 알았다. (ex. V1=2번 도시, V2=4번 도시, ... ) 근데 그게 아니라 그냥 V1 = 1번 도시, V2=2번 도시를 의미한다. 근데 이렇게 해도 되는 이유가 뭐냐면
예컨대 도시 순서를 2-4-3-1 순이라고 하자. 실질적으로 방문하는 도시는 2->4->3->1->2이다. 근데 이는 사실 1->2->4->3->1과도 동일하다. 어차피 각 비용 경로는 동일하고 총 비용 경로를 계산하는 것이니 굳이 일일이 출발 도시 바꿔가면서 복잡하게 할 필요 없이 출발 도시를 1로 고정하는 게 더욱 효율적이다.
앞서 설명했듯, 외판원 문제를 푸는 방법은 다양하다. 백준에서 나온 외판원 순회 2의 경우, 순열로도 가까스로 푸는 게 가능하다. (외판원 순회 1은 시간 초과로 인해 순열로 풀 수 X)
오늘은 DP로 외판원 순회 문제를 푸는 방법을 정리한다.
W: 주어진 비용행렬 그래프
G=(V, E) (인접행렬)
V: 주어진 모든 도시의 집합 {V1, V2, ..., Vn}
A: V의 부분집합
D[Vi][A]: A에 속한 도시를 각각 한 번씩만 거쳐서 Vi에서 V1으로 가는 최단경로 길이(앞서 소개했듯 이 문제를 풀 때 모든 시작 도시를 V1에서 출발한다고 고정했으니 최종 도착지점 역시 V1으로 고정) (DP에서 main problem)
D[Vi][A]를 구하자!고 할 때 [A]에는 V1을 제외한 모든 집합이 들어가야(V-{V1}) 한다. 왜냐하면, D[Vi][A]의 경로를 풀어서 쓰면
D[Vi][A]: V1(출발 도시 고정) => Vi => {A} => V1(도착 도시 고정)
이 되는데, 이 때 A에 V1이 들어있으면 거쳐야 할 도시가 중복으로 겹친다.
이 D[Vi][A]에 들어가는 과정에서 각 경로를 알려주는 인덱스를 반환하는 것이 P[Vi][A]이다. 얘는 Vi에서 A에 속한 다른 도시들로 가는 최단 경로 중에서 Vi 다음으로 가야 할 도시의 번호를 반환한다.
예를 들어 N=4에서 D[V1][A]: V1 => V2 => V3 => V4 => V1이 최단경로라고 하면
V1에서 V2로 가는 시점에서 P[V1][A] = 2, A = {V2, V3, V4}이다.
V2에서 V3로 가는 시점에서는 P[V2][A] = 3, A = {V3, V4}이다. 앞에서 P값이 여기서 i로 들어온다.
이렇게 경로를 알려주는 P[Vi][A]를 쭈루룩 모으면 D[Vi][A]를 계산할 수 있다는 것이 외판원을 DP로 푸는 방식이다.
1. 주어진 그래프 G=(V, E)
강의에서 제시한 그래프 예제는 위와 같다.
2. 재귀적 관계식 찾기
V = {V1, V2, V3, V4}
if A = {V3}라면? 즉, 부분집합 A가 {V3} 하나로만 구성되어 있다면?
D[V2][A] = length(V2, V3, V1) 즉, V2 입장에서 V3를 지나서 V1으로 가야 한다. (V1은 고정이고 A에서 V3를 갖고 있으니 남은 건 V2라서 Vi=V2)
if A = {V3, V4}라면?
D[V2][A] = min(length(V2, V3, V4, V1), leng(V2, V4, V3, V1)) = min(20, INF) = 20
따라서 재귀 관계식은 아래와 같다.
- 일반적으로 i != 1이고 Vi가 부분집합 A의 원소가 아니면
- D[Vi][A] = min(W[i][j] (Vi에서 Vj로 가는 비용) + D[Vj][A-{Vj}]) (Vj에서 Vj를 제외한 다른 도시로 가는데 드는 최소 비용))
- D[Vi][{}] = W[i][1], A={} (Vi에서 A에 속한 도시로 가야하는데 더이상 A가 없으면 최종 도시인 V1으로 가면 됨. 이때 A는 공집합)
(1에서 재귀가 호출되는 것을 볼 수 있다.)
즉, Vi에서 V1으로 가는 길 사이에 거쳐야 할 경로가 있다면 재귀를 호출하고(1번), 더이상 Vi와 V1 사이에 도시가 없으면(즉, 다른 도시를 이미 다 방문했다면) A는 공집합이 되고 따라서 Vi에서 V1으로 가는 비용을 반환한다.
여기서 특정 도시 j를 방문할 때마다 부분집합 A에서 방문한 도시 j1, j2, ...를 계속해서 빼내줘야 하는데, 그렇지 않으면 갔던 도시를 또 가게 된다.(DP에서 memoization)
3. 비트 마스킹: 부분집합을 표현하는 방법
본 문제에서는 부분집합 A를 연산하는 방법으로 비트 마스킹을 이용했다. 비트 마스킹은 비트를 이용해서 부분집합에 원소가 들어있는지 없는지를 표시하는 방식이다. 예를 들어 {1, 2, 3}라는 하나의 집합이 있다고 하자. 해당 집합 내 부분집합의 개수는 2^(n) = 3이다.
부분집합: {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,3}, {1,2,3}
이 부분집합을 비트 즉, 2진수로 표현하는 방식이 바로 비트 마스킹이다. 각 비트에 각 원소를 일대일 대응한다. 해당 숫자가 부분집합에 포함되면 1, 없으면 0으로 표시한다. 000(2)부터 111(2)까지 있다고 하면, 첫째 자릿수에는 3을, 두번째 자릿수에는 2를, 셋째 자릿수에는 1을 배치한다. (원소가 3개니까 비트의 자릿수 역시 3이다.)
{} == 000(2) ( 어떤 수도 없음)
{1} == 100(2) (1을 2^2의 자릿수에 배치했으니 1이 있으면 해당 자릿수에 불이 켜진다(=1로 바뀐다))
{2} == 010(2)
{3} == 001(2)
...
{1,2,3} == 111(2)
A의 기본적인 세팅은 A = V-{V1}이니까 A = V-{V1} = {V2, V3, V4}이다. (비트 연산이 편하도록 하기 위해 앞으로는 A = {V4, V3, V2} 로 적겠다.)
여기서 n = 전체 도시의 개수이므로 출발/도착지인 V1을 제외하고서 부분집합의 개수는 = 2^(n-1)이다. 그리고 모든 원소가 다 있을 때의 비트값 111(2)를 십진수로 바꾸면 7이며 이 값이 2^(n-1)-1이다. 따라서 비트 범위는 0~2^(n-1)-1까지.
Vi가 A에 원소로 포함되는지 확인하려면 어떻게 해야 할까?
A에 들어가는 Vi의 순서는 V4, V3, V2 순서로 넣는다고 했다.
2^0 자릿수 == V2
2^1 자릿수 == V3
2^2 자릿수 == V4
A에 모든 도시가 다 들어있다고 하면 (A ={V4, V3, V2}) A를 비트로 치환했을 때 111(2)가 될 것이다.
이때, 만약 V4가 A 안에 들어있는지를 확인하고 싶다고 하자. V4의 도시 넘버는 4이고, 비트로 환산했을 때의 위치값은 두번째 자리수이다(2^2). 도시 넘버와 위치값 차이가 2만큼이다.
부분집합의 유무 확인은 비트에서 진행한다. 만약 A = 111(2) 라고 하면, 이 중에서 V4==(2^2 자릿수)에 있으니 A의 2^2 자릿수에 1이 있는지를 확인하는 개념이다. (이때 논리 연산을 활용하게 되는데, 논리 연산 관련한 개념은 여기서 찾아보자.)
따라서 임의의 1(2)를 만들고, 얘를 V4에 해당하는 자릿수만큼 왼쪽으로 밀어버린다(=자릿수를 올린다.)
1. 1(2) => 100(2) (V4의 자릿수 == 2^(4(도시 넘버-2) 이니 2만큼 자릿수를 올린다)로 자릿수를 올리고
2. A &(and) 100(2) 연산을 실행한다.
3. 연산은 bool 값을 반환하며, 겹치는 게 하나 이상 있을 경우 True를 반환한다. A에 모든 도시가 있다고 한다면 111(2)와 100(2) 사이에는 2^2 자릿수가 겹치니 True를 반환할테고 이는 즉 A안에 V4가 있다는 뜻이다.
이를 일반화해서 함수를 짜면 아래와 같다.
def isIn(i, A):
if ((A & 1 << (i-2))) !=0: # <<는 왼쪽의 1을 오른쪽의 (i-2)만큼 자릿수를 올리는 연산자 / 자릿수를 내리려면 >>를 쓴다. 항상 왼쪽의 값을 오른쪽만큼 올리거나 내리는 개념.
return True
else:
return False
V4라는 도시 이름과 비트값을 십진수로 바꿨을 때의 값은 동일하기 때문에 (V4 = 100(2) (2^(2) 자릿수에 위치) 이진수로는 100(2) 위치를 표현하는데 십진수로 바꾸면 도시에 대응하는 값(4)가 된다. 이를 일반화하면 Vi에 대응하는 A의 자릿수는 i-2이기 때문에 1(2)를 i-2만큼 자릿수를 올려주는 것!
4. 차집합 구하기
이번에는 차집합을 구하자. A에서 Vj를 뺀 나머지 집합을 만드는 개념이다. 왜냐면 나중에 재귀를 돌리면서 지나온 경로를 배제해야 하니 A를 차집합으로 업데이트해줘야 한다.
diff(A, j) = A-{Vj}라고 하자.
위의 부분집합 확인할 때랑 비슷한데, not(~)개념만 알면 된다.
- 빼고 싶은 도시 넘버는 j이니 1(2)를 j-2만큼 자릿수를 올려준다. 이 이진수를 변수 t에 저장하자. (t = 1 << (j-2)) 그러면 t에는 해당 도시 넘버가 "들어있다"는 내용이 담긴다.
- 여기서는 차집합을 구하고 싶다고 했으니, ~t를 이용한다. not t는 t를 뒤집는 개념이다.
예컨대 V4를 빼고 싶다고 하자. 그러면 j=4이다.
1번을 적용하면 t = 1 << (4-2) = 100(2)이다.
2번에서 ~t (not t) == 011(2)이다. 이를 A와 & 연산을 수행해보자. A = 111(2)라고 하면
111(2) & 011(2) = 011(2)
따라서 V4가 A에서 제외된다. 이를 코드로 짜면
def diff(A, j):
t = 1 << (j-2)
return A & (~t)
5. A의 원소 개수 세기(count)
다음은 A 안에 원소 개수(=도시 개수)가 몇 개 남았는지를 세는 함수를 짜보자. 재귀를 돌리기 때문에 이걸 확인해야 count를 세면서 우리가 앞으로 몇 번 더 재귀를 돌려야 할 지를 알 수 있다. 즉, A의 원소 개수를 memoization하는 개념이다.
A의 원소가 몇 개인지 알려면 A를 비트로 치환한 뒤 이 중 각 자릿수 별로 값이 1인 걸 세면 된다.
def count(A, n): #n은 도시 넘버
count = 0
for i in range(n):
if ((A & (1 << n-2)) !=0): #해당 도시 넘버가 A 안에 있으면
count +=1 #원소 개수를 세는 count 변수의 값을 1만큼 올린다.
return count #for문 다 돌고 나서 count 값 반환
6. 경로 함수 구현
이제 거의 다 왔다..경로를 계산하는 함수를 짜보자. 여기서부터는 좀 복잡하니 함수를 끊어서 가보자.
def travel(w):
n = len(w)-1 # 전체 도시 개수
size = 2**(n-1) (#시작 도시인 V1을 제외한 n-1개 도시의 부분집합의 개수)
#D, P 각각 프레임 만들어주기 (사이즈는 (n+1) X 2**(n-1)(행: V1을 포함한 모든 도시 수 - 그래서 n+1)(열: 각 도시에서 V1과 해당 행의 도시를 제외한 다른 도시의 부분 집합 수-size)
D = [[0] * size for _ in range(n+1)] # 각 경로에 대한 최소 비용을 담고 있는 이차원 배열 D((n+1) X 2**(n-1))를 만든다. 행에는 도시(1~n)가 배치되고 열에는 전체 V에서 각 행에 대응하는 도시를 뺀 부분집합이 표시가 된다.
P = [[0] * size for _ in range(n+1)] # A에 속한 도시를 정확히 1번만 거쳐서 Vi에서 V1으로 가는 최단 경로에서 Vi 다음에 오는 첫 번째 도시의 인덱스
경로 비용을 계산하는 함수 travel(w)는 비용행렬 w를 입력으로 받아 최소 경로 값을 반환하는 함수이다.
n = len(w)-1인데, 여기서 n은 전체 도시의 개수를 의미한다. 왜 w에서 1을 빼냐면, 본 강의에서 input으로 받는 w의 모양새는 아래와 같기 때문이다. 0부터 숫자를 세는 특성을 감안해 계산을 편하게 하기 위해 테두리에 0열, 0행에 각각 -1을 둘러놨다. 이러면 w[i][j]에서 i, j가 도시 넘버와 일치하게 된다. (만약 W를 4 X 4로 하면 수식을 쓸 때는 w[i+1][j+1]로 1씩 더해줘야 함)
여기서 D를 보자. D의 사이즈는 (n+1) X (2**(n-1))이다. 행에는 각 도시 넘버가 들어가고 열에는 각 도시 넘버에서의 부분집합이 들어간다. 예컨대 D[1][4]=10은 도시 1번에서 부분집합 4를 거쳐 도시 1로 갈 때의 최소 경로 값이다.
이때 4는 무엇이냐, 4==100(2)이므로 V1=> V4 => V1으로 갈 때의 최소 경로 값이 10이라는 뜻이다. D[i][A]에서 i는 출발하는 도시 넘버, A는 부분집합을 의미하므로 A를 이진수로 바꿔서 해석해야 한다.
그러면 D[4][1]은? V4에서 A=001(2) 이니 A에는 V2만 들어있다. 따라서 V4=> V2=> V1 경로에 대한 최솟값이 4라는 뜻이다.
그런데 뭔가 이상하다. D의 사이즈는 분명 (n+1) X (2**(n-1))이라 했는데 위의 그림은 n X (2**(n-1))인데? 이는 인덱스 넘버를 맞춰주기 위한 작업으로 실질적으로 위의 이미지에는 D[0] = [0 0 0 0 0 0 0 0]이 생략되어 있다. 걍 무시하면 됨!
그럼 P는 무엇이냐? P는 D[i][A]: Vi에서 A에 속한 원소를 거쳐 V1으로 가는 최단 경로인데 이때 Vi 다음에 오는 첫번째 도시의 인덱스를 반환하는 이차원 배열이다. 최단 경로이기 때문에 D[i][A]에는 모든 경로가 이미 결정되어 있다. 따라서 D[i][A]에서 Vi로부터 A에 속한 다른 도시를 갈 때 그 도시들 중 가장 최단 경로로 가는 도시가 정해져 있으니 이를 반환한다. 이것도 일단은 프레임만 만들어 둔다.
def travel(w):
n = len(w)-1 # 전체 도시 개수
size = 2**(n-1) (#시작 도시인 V1을 제외한 n-1개 도시의 부분집합의 개수)
#D, P 각각 프레임 만들어주기 (사이즈는 (n+1) X 2**(n-1)(행: V1을 포함한 모든 도시 수 - 그래서 n+1)(열: 각 도시에서 V1과 해당 행의 도시를 제외한 다른 도시의 부분 집합 수-size)
D = [[0] * size for _ in range(n+1)] # 각 경로에 대한 최소 비용을 담고 있는 이차원 배열 D((n+1) X 2**(n-1))를 만든다. 행에는 도시(1~n)가 배치되고 열에는 전체 V에서 각 행에 대응하는 도시를 뺀 부분집합이 표시가 된다.
P = [[0] * size for _ in range(n+1)] # A에 속한 도시를 정확히 1번만 거쳐서 Vi에서 V1으로 가는 최단 경로에서 Vi 다음에 오는 첫 번째 도시의 인덱스
########여기서부터 다시########
# D,P에 값 넣어주기 1: D[i][A]에서 A가 공집합일 때 각 행의 0번째 열에 Vi => V1으로 가는 비용 대입
for i in range(2, n+1): #V2부터 Vn까지 도시에서 각각에 대해 1번 도시로 가는 비용 대입
D[i][0] = w[i][1] #A에 아무 도시도 없다면 모든 경로를 다 지나왔다는 뜻이므로 Vi에서 최종 도시인 V1으로 가면 됨. 따라서 D의 0열에서 모든 행은 Vi=>V1으로 가는 비용을 넣는다.
# D,P에 값 넣어주기 2: D[i][A]에서 A가 공집합이 아닐 떄 D[i][1]부터 최대 D[i][A]까지 비용 넣어주기
for k in range(1, n-1): #A에 원소 개수 체크. A 원소 개수는 1개부터 n-2개까지인데 이 중에서 (A 원소 개수 최대는 n-1개)
A: int
for A in range(1, size): #1부터 2**(n-1)-1까지 공집합을 제외한 모든 부분집합 (비트로 바꾸면 A 안에 뭐 들어있는지 체크 가능)
if (count(A, n) == k): A의 원소 개수가 k와 동일하면
for i in range(2, n+1): #V2부터 Vn까지 각 도시(Vi)에 대해서
if (not isIn(i, A)): #선택한 Vi가 A에 포함되지 않다면
D[i][A], P[i][A] = minimum(W, D, i, A) #D, P를 계산
#A에 모든 원소가 다 들어있는 케이스: 이때는 다른 곳에서 출발할 수 없음. 무조건 i=1에서부터 출발해야 됨. 그래서 따로 계산.
A = size -1
D[1][A], P[1][A] = minimum(W, D, 1, A) # i=1
return D, P
이제 비어있는 D, P에 값을 넣어줘야 한다. 먼저 D[i][A]에서 A==0일 때, 즉 Vi에서 가야 할 다른 도시가 없다는 뜻이므로 종착지인 V1으로 가는 비용을 넣어주면 된다.
따라서 D[i][0] = w[i][1](Vi에서 V1으로 가는 비용)이다. 이때 range가 2부터 n까지인 이유는, V1에서 V1으로 가는 비용은 이미 0으로 정해져있기 때문에 1부터 시작할 필요가 없어서이다.
다음이 좀 헷갈리는데, 이제 D[i][1]부터 D[i][size]까지 for문을 두 번 돌면서 각 행과 열에 값을 넣어줘야 한다.
k는 부분집합 A에 있는 원소의 개수를 체크한다. for문으로 돌려서 가장 작은 1개일 때부터 최대 n-2개까지이다. (전체 도시가 다 포함되어 있으면 n-1개인데 이 경우는 n=1일때만 가능한 경우이므로 따로 계산한다.)
만약 A의 원소 개수가 k개이면, D에서 출발하는 도시 넘버 i는 2부터 n까지 for문을 도는데 만약 도시 i가 A 안에 들어있지 않을 때에만(그래야 경로가 겹치지 않으니) D[i][A], P[i][A]에 각각 최단 경로비용 및 Vi 다음에 가야 할 인덱스를 저장한다.
7. 최적 함수 minimum
진짜 마지막.. 각 D, P에 대해 최소값을 구하는 minimum 함수를 짠다. 영상과 달리 본 코드는 백준 문제를 풀기 위해 짰기 때문에 약간 다르다. (W[i][j]==0이면 continue하는 건 백준 문제에서는 경로가 끊겨있을 때 W에 해당하는 경로 비용이 0으로 설정되어 있기 때문이다.)
def minimum(W, D, i, A):
minValue = 999
minJ = 1
n = len(W)-1
for j in range(2, n+1):
if (isIn(j, A)):
if W[i][j] == 0:
continue
m = W[i][j] + D[j][diff(A, j)]
if (minValue > m):
minValue = m
minJ = j
return minValue, minJ
전체 코드는 아래와 같다.
#DP solution
from sys import stdin
n = int(stdin.readline())
W = []
for i in range(n):
li = list(map(int, stdin.readline().split()))
W.append(li)
citys = []
for i in range(n):
citys.append(i)
for i in range(len(W)):
W[i].insert(0, -1)
W.insert(0, [[-1]*len(W[i])])
#부분집합을 구하는 함수
def isIn (i, A):
if ((A & (1 << (i-2)))) !=0:
return True
else:
return False
#차집합을 구하는 함수
def diff(A, j):
t = 1 << (j-2)
return (A & (~t))
#A의 원소 개수를 count하는 함수
def count(A, n):
count = 0
for i in range(n):
if ((A &(1 << i)) !=0):
count +=1
return count
#최종함수
def travel(W):
n = len(W)-1
size = 2**(n-1)
D = [[0] * size for _ in range(n+1)]
P = [[0] * size for _ in range(n+1)]
for i in range(2, n+1):
D[i][0] = W[i][1] #D[i][0]에서 [0]은 A가 공집합임을 뜻함 => W[i][1]은 vi에서 v1으로 갈때의 비용이니
for k in range(1, n-1):
A: int
for A in range(1, size):
if (count(A, n) == k):
for i in range(2, n+1):
if not (isIn(i, A)):
D[i][A], P[i][A] = minimum(W, D, i, A)
A = size -1
D[1][A], P[1][A] = minimum(W, D, 1, A)
return D, P
def minimum(W, D, i, A):
minValue = 999
minJ = 1
n = len(W)-1
for j in range(2, n+1):
if (isIn(j, A)):
if W[i][j] == 0:
continue
m = W[i][j] + D[j][diff(A, j)]
if (minValue > m):
minValue = m
minJ = j
return minValue, minJ
D, P = travel(W)
print(D[1][2**(len(W)-2)-1])
'정글사관학교 개발일지 > 자료구조&알고리즘' 카테고리의 다른 글
| 정글사관학교 11일차 TIL: 숫자 야구(#2503), 독일 로또(#6603) (0) | 2021.11.12 |
|---|---|
| 정글사관학교 10일차 TIL: 안전 영역 문제 풀이, 정렬 알고리즘 정리(버블 정렬, 선택 정렬, 삽입 정렬, 힙 정렬) (0) | 2021.11.11 |
| 정글사관학교 9일차 TIL: BFS & DFS, 큐와 스택 (0) | 2021.11.10 |
| 정글사관학교 6일차 TIL: 재귀, 정렬 알고리즘 (0) | 2021.11.07 |
| 정글사관학교 4일차 TIL: 알고리즘 풀이, 문제해결이란 무엇인가 (0) | 2021.11.06 |