지난 알고리즘 주차때 비트마스킹을 활용해서 외판원 순회 문제의 연산량을 획기적으로 줄였던 적이 있다.

https://www.acmicpc.net/problem/2098
외판원 순회2에서 비해 메모리/시간만 줄었을 뿐인데 골드 1이 되었다.

이 외판원 순회와 같은 n! 문제들은 시간과 메모리에 상당히 민감하다.
이번에 풀 문제 또한 총 20!의 연산을 해야되는데
20! = 2432902008176640000 이라는 엄청난 숫자가 나온다.

그냥 브루트포스처럼 하나하나 계산하다가는
컴퓨터가 죽던 내가 죽던 하나는 죽는다는 소리다.
1초에 3억번 연산하면 260년이라는 시간이 걸리기 때문이다.

끔찍한 상상은 그만하고 문제를 보자.

백준 1311번 할 일 정하기
https://www.acmicpc.net/problem/1311

문제
N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다.

사람은 1번부터 N번까지 번호가 매겨져 있으며, 일도 1번부터 N번까지 번호가 매겨져 있다.

Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력
첫째 줄에 사람과 일의 수 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 D의 내용이 주어진다. 비용은 10,000보다 작거나 같은 자연수이다.

출력
모든 일을 하는데 필요한 비용의 최솟값을 출력한다.

코드

N = int(input())
table = [list(map(int,input().split())) for _ in range(N)]

dp = {}

def cal(number,work):
    if(number,work) in dp:
        return dp[(number,work)]
    if work == (1 << N) - 1 :
        return 0
    min_cost = int(1e9)
    for i in range(N):
        if work & (1 << i):
            continue
        cost = cal(number+1,work | (1 << i)) + table[number][i]
        min_cost = min(cost,min_cost)
    dp[(number,work)] = min_cost
    return min_cost

print(cal(0,0))

비트마스킹을 활용한 dp 문제는 풀이법이 간단하다.
물론 지금껏 풀어본게 외판원순회와 이 문제 밖에 없으니까 그런지는 몰라도
난이도에 비해서는 확실히 간단하다.

길게 설명하지 않고 짧고 간단하게 코드리뷰만 하고 넘어가자.

tabulation

dp = {}

이 문제는 중복계산을 막아야된다. 그래서 tabulation을 활용하게 되는데, 비트마스킹으로 이때까지 했었던 일을 모조리 상수 하나에 저장할 수 있게 되니, 딕셔너리의 key/value로 묶어도 잘 굴러간다.
tabulation을 쓰지 않으면 처음 연산에서 시간초과가 뜬다...

비트마스킹

for i in range(N):
        if work & (1 << i):
            continue
        cost = cal(number+1,work | (1 << i)) + table[number][i]
        min_cost = min(cost,min_cost)

간단하다. visited = True 같은 이런 방법을 쓰지 말고
그냥 work(1 << i) 이거 하나 쓰면 문제 꼬일일도 없이 시간과 메모리를 cost 없는 수준으로 날로 먹을 수 있다.
물론 beat연산이라 N이 100개 1000개 넘어가게 되면 사용하지 못하겠지만 N = 20수준에서는 잘 사용 할 수 있다.

여담

비트마스킹은 정말 간단하면서도 강력한 무기이다.
지금 수준에서 N!을 감당할 수 있는 유일한 방법이기도 하고,
무엇보다도 따로 리스트 만들어서 채크하고 if문 돌리고
그럴 필요도 없어지니 코드도 간단해진다.

비트마스킹을 안해봤다면 꼭 공부하길 추천한다.