[SW 정글] 백준 2098 외판원순회 - 비트마스킹(feat, Python)

잡설

이번 주차는 동적프로그래밍과 그리디 알고리즘에 대해 공부하고 문제를 푼다.

 

dp문제는 풀 때마다 항상 다른 게 나오는 것 같다.

 

몇 문제 안 풀어 봣지만, 문제를 보고 어떤 알고리즘인지 아는 것이 중요할 것 같다.

 

Kanpsack problem, bitmasking, LIS(Longest Increasing Subsequence), LCS(Longest Common Subsequence)

등이 있다.

 

다양한 문제들을 풀어보고 다양한 알고리즘들의 풀이법을 익히는 것이 중요할 것 같다.

 

위 4개의 알고리즘 문제를 만났을 때, 가장 어려웠던 bitmasking문제를 기록해놓으려한다.

 

---

정답 코드

import sys
sys.stdin = open(‘input.txt’)

N = int(sys.stdin.readline())

W = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

for i in range(N):
    for j in range(N):
        if W[i][j] == 0:
        	# 최소비용을 구하는 문제이기 때문에 0 대신 큰값(1e9)을 설정
            W[i][j] = 1e9

# 1 << N  == 2**(n-1)-1
dp = [[1e9]*N for _ in range(1<<N)]
dp[0][0] = 0

# 0(출발) -> S(을 거쳐서) -> i(도착지)
# S : 경유지 집합
for S in range(1<<N):
	# i : 도착지
    for i in range(N):
    	# j도시 빼기
        for j in range(N):
            if S & (1<<j):
 				# 👇아래에서 설명
                dp[S][i] = min(dp[S][i], dp[S&(~(1<<j))][j] + W[j][i])

print(dp[-1][0])

 

코드가 개쩔기 때문에 흥미를 유발하기 위해 먼저 올렸다.

 

 

문제

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

2098번: 외판원 순회

 

 

풀이법

먼저 문제를 읽어보면 "한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획"

이라고 한다.

 

예를 들어 총 도시는 4, 최단경로는 01230이라 했을 때, 출발도시가 0인 경우 0 -> 1 -> 2 -> 3 -> 0 이고

출발도시가 2이라 가정했을 때도  2 -> 3-> 0 -> 1 -> 2 이다.

 

즉, 출발도시가 달라도 경로는 똑같고 거기서 발생하는 비용도 똑같다는 것이다.

 

그래서 나의 풀이에서는 시작점을 무조건 0으로 잡을 것이다.

 

그리고, 경유지(지나는 도시)를 비트마스킹을 통해 표현할 것이다.

 

예를 들어

 

001 -> 0번(인덱스) 도시만을 경유

 

010 -> 1번 도시만을 경유

 

101 -> 2번과 0번 도시만을 경유

 

 

위와 같이 어느 도시들을 지나갔는지 비트마스크로 표현할수 있다.

 

이제 마지막으로 대망의 점화식을 짜면 된다..

그전에 파이썬의 비트 연산자를 알아보도록 하자

---

S & (1 << j)

<<연산자는 지정한 수만큼 비트를 전부 왼쪽으로 이동시키는 left shift 연산이다.

즉, 2진수에서 모든 수를 왼쪽으로 지정한 수만큼 이동시키는 것이다.

ex) 1<< 2 = 100, 101 << 2 = 10100

 

S | (1 << j)

|은 OR연산이다. 비트 중 하나라도 1이 존재한다면 1을 반환한다.

 

S & (~(1<<j)

~ 연산자는 NOT 연산이다. 비트가 0이라면 1, 1이라면 0을 반환한다.

 

---

이제 진짜 점화식을 알아보도록 하쟈

 dp[S][i] = min(dp[S][i], dp[S&(~(1<<j))][j] + W[j][i])

0번 도시에서 S를 거쳐 i로 가는 값 == 0번도시에서 j를 뺀 S도시를 거쳐 j에 갈 수 있는 최소 비용 + j도시에서 i도시로 가는 비용이다.

 

 

0번도시에서 j를 뺀 S도시를 거쳐 j에 갈 수 잇는 비용은 앞에서 dynamic programming을 통해 최소값을 구했기 때문에 결과값도 최소가 될 것이다.

 

 

최종 제출 코드

import sys
sys.stdin = open(‘input.txt’)
N = int(sys.stdin.readline())
W = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
for i in range(N):
    for j in range(N):
        if W[i][j] == 0:
            W[i][j] = 1e9
dp = [[1e9]*N for _ in range(1<<N)]
dp[0][0] = 0
for S in range(1<<N):
    for i in range(N):
        for j in range(N):
            if S & (1<<j):
                dp[S][i] = min(dp[S][i], dp[S&(~(1<<j))][j] + W[j][i])
print(dp[-1][0])

 

개쩐다... 이상으로 우리 반의 기둥 형규형에게 들은 풀이법이었다.

 

---

​

자, 그럼 나의 개막장 같은 코드를 보쟈

 

그 전에 비트마스킹을 처음 접해보는 나에게 기깔나게 설명해주신 분의 강의를 추천드린다.

 

https://www.youtube.com/watch?v=wj44Dd0zdzM&t=1s 

 

 

위 강의에서 말하는 핵심은  5가지다

 

1. A의 원소 개수가 몇개인지 확인하는 함수

2. i가 A에 포함되는 지 여부

3. 차집합 구하기

4. 최소값 구하기

5. 최소 비용 구하며 경로 찾기

 

위 코드에서는 출발점을 0 으로 했지만 이 코드에서는 출발점이 1이다. 그래서 A의 첫번째 열과 첫번째 행은 모두 -1이다.

 

코드 - (오답)

import sys

input = sys.stdin.readline

# A의 원소 개수가 몇개인지
def count(A, n):
    count = 0
    for i in range(n):
        if ((A & (1 << i)) != 0):
            count += 1
    return count

# i가 A에 포함 여부
def isIn(i, A):
    # v2부터 시작이니까 i-2
    # ex) 1 0 1
    # -> v4(o) v3(x) v2(o)
    if((A & (1 << (i-2))) != 0):
        return True
    return False

# 차집합 구하기
def diff(A, j):
    t = 1 << (j-2)
    return (A & (~t))


def minimum(W, D, i, A):
    minValue = INF
    minJ = 1
    n = len(W) - 1
    for j in range(2, n + 1):
        if isIn(j, A):
            m = W[i][j] + D[j][diff(A, j)]
            if minValue > m:
                minValue = m
                minJ = j
    return minValue, minJ


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]
    for k in range(1, n-1):
        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


N = int(input())

INF = 1e9
W = [[-1] * (N+1)]
# W = [[int(x) for x in input().split()] for _ in range(N)]
for _ in range(N):
    tmp = [-1]
    tmp.extend(int(x) for x in input().split())
    W.append(tmp)

D, P = travel(W)
print(D[1][2**(len(W)-2)-1])

 

교수님의 설명을 열심히 듣고 풀었지만 '틀렸습니다'를 받았다 ㅠ

 

사실 왜 틀렸는지 잘 모르겠다. 이 글을 쓰고 찾아볼 예정이다.

 

 

어제부터 오늘까지 계속 공부하고 있는데, 제일 어려운 알고리즘 인것 같다.

 

어제 오늘 공부한걸 까먹지 않게 기록해놓고 비슷한 문제 있으면 이 풀이를 적용해보도록 해야겠다!

 

 

 

나도 비트마스크에 대해 완전히 이해한 건 아니라 그런가 설명이 강아지똥 같다,,, 독자들에게 양해 부탁드린다

 

오늘도 모두 열코다 🔥 , 🔥!!!