#28 동적 계획법(Dynamic Programming) 3 - 비트마스크(Bit Mask)

 이번에는 이전에 다룬 바 있는 비트마스크 기법을 동적 계획법에 적용하여 몇 가지 문제를 해결해본다.

 

1. 할 일 정하기 1 (https://www.acmicpc.net/problem/1311)

 N명의 사람과 N개의 일이 있으며 i번째 사람이 j번째 일을 했을 때의 비용이 D[i][j] 라고 할 때, 한명의 사람이 하나의 일을 담당하도록 분배하되 총 처리비용이 최소값이 되도록 하는 경우를 찾는 문제

 

 가장 먼저 떠오르는 해법은 완전탐색이다. 각 일마다 일을 맡지 않은 사람중 하나를 할당한 뒤 그 사람은 일을 맡았음을 표시하고 다음 일로 넘어가는 방식으로 완전탐색을 진행하면 답을 쉽게 찾을 수 있다.  하지만 이 방식을 그대로 사용하면 O(N!) 의 시간복잡도를 보여, N의 크기가 최대 20까지 늘어나는 이 문제에서는 당연히 시간초과가 발생한다.

 

 이를 해결하기 위해서는 메모이제이션을 통해 중복연산을 방지해야한다. k가 이번 단계에서 해결해야할 문제번호, visited가 각 사람들이 일을 맡고있는지 여부를 나타낸 배열이라고 할 때, dp[k][visited]는 사람들의 상태가 visited 와 같고 k번째 문제를 해결해야하는 시점에서 앞으로 모든 일을 처리하기 위해 필요한 비용의 최솟값이 되어야한다. 

 

문제는 visited의 취급이다. visited로 배열, 리스트 등의 자료구조를 사용하기에는 메모이제이션에 어려움이 많다.  예를 들어 Python의 경우 딕셔너리를 사용하려고 해도 리스트는 mutable한 자료구조이기 때문에 딕셔너리의 키 값으로 사용할 수 없다.  immutable한 자료구조인 튜플을 사용하기엔 visited를 변경할때 마다 전체를 새로 만들어야하는 오버헤드가 발생한다.  리스트를 문자열화하여 키 값으로 사용하는 것도 오버헤드가 크기 때문에 어렵다.  여기서 비트마스크를 사용하면 n이 20일 경우 0 이상 2^20 이하의 정수로 visited를 표현할 수 있기 때문에 모든 문제를 해결할 수 있다.  비트마스크를 적용하여 이 문제를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol1311():
    # 일과 사람의 수
    n = int(input())
    
    # c[i][j] 는 i 번째 사람이 j 번째 일을 할 경우 드는 비용
    c = [list(map(int, input().split())) for _ in range(n)]
    
    # dp[t][visit] 는 t 번째 문제를 풀 차례이며 사람들의 상태(일을 맡았는지 아닌지)가
    # visited일 때 모든 일을 처리하기 위해 앞으로 필요한 비용의 최솟값
    dp = [[-1]*(1<<n) for _ in range(n)]
    
    # 완전탐색 함수
    def dfs(t, visit):
        # 모든 문제를 해결했다면 앞으로 필요한 비용은 0
        if t == n:
            return 0
            
        # 아직 계산한 적이 없는 단계일 경우
        if dp[t][visit] == -1:
            # 일을 맡지 않은 사람 하나를 택해 다음단계로 넘어가는 경우 중 
            # t번째 일의 처리비용과 남은 일의 처리비용의 합의 최솟값이 dp[t][visit] 가 된다.
            dp[t][visit] = min([dfs(t+1, visit|(1<<p)) + c[p][t] for p in range(n) if not (visit & 1<<p)])
        
        # 남은 문제를 해결하기 위한 최소비용 반환
        return dp[t][visit]
        
    # 첫 번째 문제를 해결해야 하고 아무도 일을 맡지 않은 상황에서부터 탐색하여 최소비용을 반환
    return dfs(0, 0)

이 코드의 경우 일반적인 언어라면 AC를 받을 수 있는 풀이지만 Python3의 경우 시간초과가 발생한다.  PyPy3으로 제출할 경우에는 AC를 받을 수 있었다.  이 문제는 동적계획법보다 효율적인 해법(헝가리안 알고리즘)이 존재하지만 그에 대해서는 나중에 다루기로 한다.

 

 

2. 외판원 순회(https://www.acmicpc.net/problem/2098)

 1번부터 N번까지의 도시가 있고 도시 사이에 길이 있을 때(길이 없을 수도 있음), 한 도시에서 출발하여 모든 도시를 방문한 뒤 처음 도시로 돌아오기 위한 최단경로를 구하는 문제. 단, 출발한 도시로 돌아올 때를 제외하고는 같은 도시를 두 번 방문할 수 없다.

 

 1번 문제와 거의 유사하게 해결 가능한 문제이다. 현재 위치 cur, 도시의 방문여부 visited 에 대해 dp[cur][visit]은 현재  cur 도시에 있고 방문 상태가 visited 와 같을 때 모든 도시를 거쳐 처음 도시로 돌아가기 위해 필요한 비용의 최솟값이 되도록 한다.  1번 문제와 다른 점은 모든 도시를 방문한 뒤 처음 도시로 돌아가는 최소비용을 구하는 것이기 때문에 모든 도시를 방문한 상태에서 dfs(x, visited)가 0을 반환하는 것이 아니라 x에서 처음 도시로 가는 비용을 반환해야한다는 점이다. 이를 구현한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline
INF = 10 ** 9


def sol2098():
    # 도시의 갯수
    n = int(input())
    
    # 각 도시로부터 다른 도시로 가는데 드는 비용
    # 0일 경우 갈 수 없음을 의미하기 때문에 비용을 INF로 함
    w = [list(map(int, input().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if w[i][j] == 0: w[i][j] = INF

	# dp[i][visited] 는 현재 i번째 도시에 있고 도시의 방문상태가 visited 일 때
    # 남은 도시를 모두 방문한 뒤 처음 도시로 돌아가는데 드는 비용의 최솟값이 된다.
    dp = [[-1] * (1 << n) for _ in range(n)]
    
    # 모든 도시를 방문한 상태의 visited값
    complete = (1 << n) - 1
    
    # 완전탐색 함수
    def dfs(cur, visited):
        # 만약 모든 도시를 방문했다면
        # 현재 위치에서 처음 도시로 가는 데 드는 비용을 반환
        if visited == complete:
            return w[cur][0]
            
        # 아직 계산하지 않은 경우라면
        if dp[cur][visited] == -1:
            # 다음 도시로 가는거리 w[cur][i] 와 다음 단계dfs(i, visited|(1<<i))의 합 중
            # 가장 작은 값이 dp[cur][visited] 가 된다.
            res = INF
            for i in range(1, n):
                check = 1 << i
                if w[cur][i] and not (visited & check):
                    res = min(res, dfs(i, visited|check) + w[cur][i])
            dp[cur][visited] = res
            
        # 현재 cur 도시에 있고 방문 상태가 visited일 때 
        # 모든 도시를 거쳐 처음 도시로 돌아가기 위한 최소비용을 반환
        return dp[cur][visited]
	
    # 어느 점을 시작점으로 잡더라도 외판원 문제의 정답은 같다
    # 만약 한 점에서 순회경로를 찾지 못한다면 방문할 수 없는 점이 존재한다는 의미이기 때문에
    # 그 그래프에서는 순회경로가 존재하지 않는다
    return dfs(0, 1)

외판원의 순회 문제는 유명한 NP문제 중 하나로 동적계획법을 적용하더라도 그다지 빠른 속도를 기대하긴 어렵기에, 보통은 최적해를 찾는 대신 그리디 알고리즘으로 최적해에 근사한 값을 찾아 활용한다고 한다.  이 문제에서는 N의 크기가 16으로 제한적이기 때문에 동적계획법으로도 AC를 받을 수 있었다. 

 

 

3. 박성원 (https://www.acmicpc.net/problem/1086)

 서로 다른 정수로 이루어진 집합이 주어졌을 때, 집합의 순열을 이어붙여 만든 정수가 k로 나누어 떨어질 확률을 구하는 문제. 실제로 순열을 구하려고하면 O(N!)이라는 엄청난 시간복잡도를 보이기 때문에 당연히 시간초과가 발생한다. 어느 숫자들을 합쳤는지 비트마스크로 표현하여 동적계획법으로 접근해야한다.  여기서 중요한 포인트는 동적계획법으로 어떤 정보를 저장하느냐이다. 

 

 12와 35를 7로 나누는 경우를 생각해보자.  1235를 7로 나눈 나머지는 3이다.   35 부분을 건드리지 않는 7의 배수 700으로 1200을 나누면 나머지는 500이 된다. 남은 535는 결국 1235에서 7의 배수를 뺀 것이기 때문에 7로 나눈 나머지는 1235와 같다.  그리고 1200을 700으로 나눈것은 결국 붙이는 두 수중 앞쪽의 12를 7로 나눈 것과 같다.  즉, 두 수 a와 b를 이어붙여 ab 로 만들고 이를 k로 나눈 나머지는 a를 k로 나눈 나머지 c와 b를 이어붙여 cb로 만든 뒤 k로 나눈 나머지와 같다.

 

위 사실에 근거하여, 비트마스크 i로 어느 숫자들을 골랐는지 표현하고, 그 숫자들로 이루어진 순열에서 만들어진 수를 k로 나눈 나머지가 j인 경우의 수가 dp[i][j] 가 되도록 하면, dp[i][j] 로부터 다음에 이어질 숫자를 골라 나머지와 붙인다음 또다시 나머지를 구하는 것으로 dp 배열을 채워나갈 수 있다. 이를 구현한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol1086():
    # 집합의 크기(수의 갯수)
    n = int(input())
    
    # 집합 s
    s = [int(input()) for _ in range(n)]
    
    # 만들어진 수를 나눌 수 k
    k = int(input())
    
    # m[i][j] 는 j 와 i번째 수를 이어붙인 숫자를 k로 나눈 나머지
    m = [[((j * (10 ** len(str(s[i])))) % k + s[i] % k) % k for j in range(k)] for i in range(n)]

	# dp[i][j] 는 수의 선택상태가 i와 같을 때 순열로 만들어지는 수를 k로 나눈 나머지가 j인 경우의 수
    dp = [[0] * k for _ in range(1 << n)]
    
    # 아무것도 고르지 않았을 때 나머지가 0인 경우의 수를 1로 초기화
    dp[0][0] = 1
    
    # 상태전이 시작
    for i in range((1 << n) - 1):
        for j in range(k):
            # 현재 상태에서 나머지가 j인 경우의 수가 0이라면 이로부터 파생되는 경우의 수도 0
            # 더이상 진행할 필요가 없음
            if dp[i][j] == 0:
                continue
                
            # 아직 고르지 않은 수에 대해
            for b in range(n):
                check = 1 << b
                if not (i & check):
                    # 나머지 j와 이 수를 합친 수를 k로 나눈 나머지는 m[b][j]
                    # 현재 상태의 경우의수가 그대로 dp[i | check][m[b][j]]로 전이되기 때문에
                    # 현자 상태의 경우의 수를 더해줌
                    dp[i | check][m[b][j]] += dp[i][j]

    # dp[(1<<n)-1] 까지 전이가 종료되고나면
    # 주어진 집합 전체의 순열로 이루어진 수를 k로 나눈 나머지가 
    # 각각 0 ~ k-1 인 경우의 수를 모두 얻을 수 있다.
    # 그 경우의 수를 모두 더한것이 전체 경우의 수 (w)
    # 그 중 나머지가 0인 것이 k로 나누어 떨어지는 경우의 수 (v)
    v = dp[-1][0]
    w = sum(dp[-1])
    
    # 구하려는 것은 v / w 를 기약분수 형태로 나타낸 문자열
    # 기약분수로 나타내기 위해서는 v와 w의 최대공약수르 둘을 나누어준 뒤 출력형식에 맞춰 반환한다.
    g = gcd(v, w)
    return f'{v // g}/{w // g}'


# 유클리드 호제법에 따라 최대공약수를 구하는 함수
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

동적계획법을 어떻게 적용할지 찾아내기가 굉장히 까다롭고 두 수를 이어붙일 때 앞쪽 수의 나머지를 이용한다는 발상 또한 필요해서 상당히 어려운 문제였다.  비트마스크를 통한 동적계획법으로 상태전이를 표현하는 기법이나 두 수를 이어붙인 수의 나머지에 대한 발상 등은 활용될 여지가 충분해보이니 기억해둘 필요가 있는 문제인 것 같다.