코드
import sys
def solution(N, W, dp):
for i in range(N):
for j in range(N):
if not W[i][j]:
W[i][j] = float('inf')
for i in range(1, N):
dp[i][0] = W[i][0]
for k in range(1, N - 1):
for route in range(1, size):
if count(route, N) == k:
for i in range(1, N):
if not isin(i, route):
dp[i][route] = get_minimum(N, W, i, route, dp)
dp[0][size - 1] = get_minimum(N, W, 0, size - 1, dp)
return dp[0][size - 1]
def count(route, N):
cnt = 0
for n in range(1, N):
if route & (1 << n - 1) != 0:
cnt += 1
return cnt
def isin(i, route):
if route & (1 << i - 1) != 0:
return True
else:
return False
def get_minimum(N, W, i, route, dp):
minimum_dist = float('inf')
for j in range(1, N):
if isin(j, route):
before_route = route & ~(1 << j - 1)
dist = W[i][j] + dp[j][before_route]
if minimum_dist > dist:
minimum_dist = dist
return minimum_dist
N = int(sys.stdin.readline())
W = [list((map(int, sys.stdin.readline().split()))) for _ in range(N)]
size = 2 ** (N - 1)
dp = [[float('inf')] * size for _ in range(N)]
print(solution(N, W, dp))재귀를 이용한 코드
import sys
N = int(sys.stdin.readline())
W = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [[0] * (1 << N - 1) for _ in range(N)]
def solution(i, route):
if dp[i][route] != 0:
return dp[i][route]
if route == (1 << (N - 1)) - 1:
if W[i][0]:
return W[i][0]
else:
return float('inf')
min_dist = float('inf')
for j in range(1, N):
if not W[i][j]:
continue
if route & (1 << j - 1):
continue
dist = W[i][j] + solution(j, route | (1 << (j - 1)))
if min_dist > dist:
min_dist = dist
dp[i][route] = min_dist
return min_dist
print(solution(0, 0))분명 전에 완전탐색으로 풀었던 문제인데 더 어려워진 모습으로 만나게 되었다.
비트마스킹이라는 처음 듣는 개념을 체화하기 위해 유튜브로 교수님들의 강의를 찾아들으며 열심히 노력했는데 아직도 조금 어색하다. 이 포스팅을 성공적으로 마무리할 수 있었으면 좋겠다.
풀이
먼저 문제에서 항상 순회할 수 있는 경우만 주어진다고 했으므로 어느 한 점을 임의로 잡아서 그 점에서 시작해 최소비용으로 다시 돌아오는 경로를 찾으면 된다.
왜냐하면 만약 점 2에서 시작할 때 2 -> 1 -> 3 -> 2 가 최소 비용 경로라고 한다면 1에서 시작할 때도 1 -> 3 -> 2 -> 1 이라는 동일한 최소 비용 경로가 존재하기 때문이다.
그리고 이번 문제에서는 비트마스킹을 사용해 방문체크를 한다.
비트마스킹을 이용했을 때의 장점은 크게 3가지가 있다.
비트마스킹의 장점
- 빠른 수행시간
- 컴퓨터와 가까운 2진수를 사용하기에 연산속도가 굉장히 빠르다고 한다.
하나의 연산만 놓고 보면 10진수와도 차이가 크지 않겠지만 연산을 굉장히 많이 수행하는 상황에는 눈에 띄는 차이를 볼 수 있을 것이다.
- 적은 메모리
- 쉽게 말해 10bit짜리 이진수 하나로 210가지의 경우의 수를 표현이 가능하다.
아래와 같은 방문을 체크하는 배열을
[1, 0, 0, 1, 1, 1, 0, 0, 1, 1]
1001110011와 같이 이진수 하나로 표현할 수 있는 것이다.
- 비트 연산자를 이용한 짧고, 깔끔한 코드
다시 문제 풀이로 돌아오면 방문해야하는 점들 만큼의 길이를 가진 2진수를 만들어 이를 이용해 방문한 점들을 체크하는 것이다.
예를 들어 2진수 10(= 2)은 두 번째 점을 방문했다는 뜻이다.
이어서 2진수 110(= 6)은 두 번째, 세 번째 점을 방문했다는 뜻이다.
이제 이를 이용해 문제를 풀어보겠다.
진짜 풀이
먼저 시작점을 가장 첫 번째 점인 0으로 잡겠다.
이어서 dp[i][route]를 i에서 route에 들어 있는 점들을 지나 0로 향하는 최소비용이라고 정의하겠다.
문제의 예제로 몇가지 예를 들어보자면 아래와 같다.
그래서 점이 4개인 이 예제에서는 dp[0][7] = dp[0][111] (= 0에서 출발해 첫 번째, 두 번째, 세 번째 점을 지나 다시 0으로 돌아갈 때 최소 비용)을 구하면 순회하는데 필요한 최소비용을 얻을 수 있다.
이제 코드를 하나씩 뜯어보자.
먼저 최소 비용 경로를 구할 때 사용하는 get_minimum 함수에 대해 알아보자.
def get_minimum(N, W, i, route, dp):
minimum_dist = float('inf')
for j in range(1, N):
if isin(j, route):
before_route = route & ~(1 << j - 1)
dist = W[i][j] + dp[j][before_route]
if minimum_dist > dist:
minimum_dist = dist
return minimum_dist이 함수의 반환값은 dp[i][route]에 들어가게 되는데 위에서 봤던 dp[1][6]를 이 함수를 이용해 구해보자.
함수에서 i는 1이고 N은 총 점의 개수인 4, route = 6 이를 이진수로 나타내면 110이 된다.
먼저 for문을 돌면서 route에 들어있는 점 중 1에서 갈 수 있는 점을 찾는다.
이때 isin 함수를 사용하는데 if route & (1 << i - 1) != 0 비트연산을 이용한 조건문을 통해 route에 들어있는지 여부를 확인한다.
여기서 우리는 route에 들어있는 점 2와 3을 찾을 수 있는데 이를 이용해 두 개의 경로의 비용을 구할 수 있다.
W[1][2] + dp[2][route - 2] 와 W[1][3] + dp[3][route - 3] 인데 이때 route - 2, route - 3은 기존 route에서 각각 점 2, 점 3을 뺀 route를 뜻한다.
이 역시 route & ~(1 << j - 1)와 같이 비트 연산자를 이용해 구한다.
W[1][2] + dp[2][route - 2] 를 간단히 설명하자면 먼저 점 1에서 2로 가고 점 2에서 route에 있는 점들을 방문한 뒤 점 0으로 가는 비용을 뜻한다. 이때 route는 기존의 route에서 점 2가 빠졌으므로 점 3만 들어있다.
이렇게 구한 두 비용 중 최소 비용이 dp[1][6]의 값이 된다.
이제 전체 코드를 확인하겠다.
먼저 0으로 되어있는 경로들은 갈 수 없는 경로이기에 비용이 0인 경로로 사용되지 않도록 float('inf')로 갱신해준다.
이어서 dp[모든 점][0]에 값들을 채워준다.
for i in range(N):
for j in range(N):
if not W[i][j]:
W[i][j] = float('inf')
for i in range(1, N):
dp[i][0] = W[i][0]
#점 i에서 바로 점 0으로 가는 비용그리고 우리는 앞서 get_minimum에서 봤듯이 점이 2개 들어있는 route를 이용한 값을 얻기 위해서는 점이 1개 들어있는 route를 이용한 값들이 필요하다.
따라서 점이 1개 들어있는 route를 이용한 값부터 점이 N - 2개(시작점과 자기 자신을 제외한 모든 점)이 들어있는 route를 이용한 값까지 순서대로 얻어야 한다.
for k in range(1, N - 1): #점 1개 들어있는 route부터 N - 1개 들어있는 route까지
for route in range(1, size):
if count(route, N) == k: #점이 k개 들어있는 route 찾기
for i in range(1, N):
if not isin(i, route):
dp[i][route] = get_minimum(N, W, i, route, dp)이제 마지막으로 dp[0][2 ** (N - 1) - 1]의 값을 구하면 문제를 해결할 수 있다.
dp[0][size - 1] = get_minimum(N, W, 0, size - 1, dp)
#size = 2 ** (N - 1) - 1이때 2 (N - 1) - 1는 시작점을 제외한 모든 점이 들어있는 route**를 뜻한다.
예를 들어 N = 5일 때는 2진수 1111 = 15가 된다.
재귀를 이용한 코드는 이보다 훨씬 간단한데 위 내용을 이해할 수 있으면 어려움 없이 이해할 수 있을 것이다.
dp문제들을 풀면서 이와 유사한 형태로 재귀를 구현한 코드를 많이 볼 수 있었다. dp문제를 풀 때 유용할 것 같은데 조만간 관련해서 포스팅을 해봐야겠다.
마지막으로 이번 문제를 푸는 데 사용한 비트연산을 간단히 알아보자.
A & (1 << B)
먼저 << 는 지정한 수만큼 비트를 전부 왼쪽으로 이동시키는 left shift 연산이다
쉽게 말하자면 2진수에서 모든 1을 옆으로 지정한 수만큼 이동시키는 것이다.
예를 들어 1 << 2 = 100, 101 << 2 는 10100이 된다.
당연히 오른쪽으로 이동시키는 right shift 도 존재한다.
이어서 &은 대응되는 비트가 모두 1이면 1을 반환하는 비트 AND 연산이다.
10101 & 10011 = 10001
A | (1 << B)
다음으로 | 는 대응되는 비트 중에서 하나라도 1이면 1을 반환하는 비트 OR연산이다.
10000 | 1111 = 11111
A & ~(1 << B)
마지막으로 ~는 비트를 1이면 0으로, 0이면 1로 반전시키는 비트 NOT연산이다.
~10100 != 1011
~10100 = 11101011
이것만 공부하니 하루가 지나갔다.
오늘이 아쉬워서라도 절대 잊어버리면 안되겠다.
참고 - https://www.youtube.com/watch?v=wj44Dd0zdzM
피드백 환영합니다.
-끝-
졸라 멋있습니다...