백준 1311번 : 할 일 정하기 1 in Python

1311번: 할 일 정하기 1

 

www.acmicpc.net

이 문제는 N명의 사람에게 N개의 일을 하나씩 담당하게 할 때 모든 일을 하는데 필요한 비용의 최솟값을 구하는 문제이다.

만약 단순히 모든 경우의 수를 고려해 일을 배분한다고 하면 N!가지의 경우의 수를 모두 고려해야 하므로 총 걸리는 시간은 O(N^N)으로 매우 비효율적이다. 그래서 이 문제는 dynamic programming을 활용해 보다 효율적인 알고리즘을 생각할 필요가 있다.

즉, 이전에 계산한 결과를 저장할 배열을 만들 필요가 있는데, 이 계산 결과라 함은 일을 맡긴 사람의 수 i와 각 사람마다 맡긴 일의 집합 S에 대해 가능한 비용 중 최솟값을 의미한다. 예를 들어 N = 6일 때 4명의 사람에게 1, 3, 4, 6이라는 일을 맡겼다면 가능한 4! = 24가지의 경우 중 가장 작은 비용을 배열의 (4, {1, 3, 4, 6}) entry에 저장하고 있다. 여기서 배열의 열 인덱스를 집합으로 나타내었는데, 원래는 이러한 표현이 불가능하다. 하지만 이 집합을 숫자로 표현한다면 문제가 되지 않는다. 이를 위해 비트마스크를 사용한다. 예를 들어 {1, 3, 4, 6}의 경우 101101로 표현한다.

이제 위에서 만든 배열을 dp라 하자. 그러면 dp의 크기는 N*(2^N)이 될 것이다. 왜냐하면 가능한 집합의 경우의 수가 2*N가지이기 때문이다. dp의 각 entry의 초기값은 아직 어떤 값을 저장하지 않았다는 의미로 -1로 한다.

그 다음에는 1번째 사람부터 일을 할당하면서 그 결과를 dp에 저장해야 하는데, 이를 구현하기 위해서 DFS를 사용한다. DFS를 함수로 구현하기 위해 dp의 행(u)과 열(visited)의 인덱스를 주면 그에 해당하는 entry의 값을 반환하는 함수 dfs를 만든다. 만약 인자로 주어진 열의 인덱스가 (1 << N) - 1이면, 모든 사람에게 모든 일을 배분했으므로 0을 반환한다. 그리고 만약 dp에 이미 저장해둔 값이 있다면 그 값을 반환한다. 위 두 가지 경우가 모두 아니면 dp의 해당 entry의 값을 무한대의 값으로 바꾸고 모든 일을 순회하면서 열의 인덱스와 일 사이에 and 연산을 수행해 0인 경우, 즉 아직 할당되지 않은 일인 경우 dp[u][visited]의 값을 기존 값과 dfs를 재귀적으로 호출한 결과에 비용을 합한 값과 비교해 더 작은 값으로 수정한다. 그러면 dp[0][0]에는 모든 사람들에게 일을 할당했을 때 비용의 최솟값이 저장된다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
N = int(input())
D = []
for _ in range(N):
    D.append(list(map(int, input().split())))
# dynamic programming을 위한 배열
dp = [[-1] * (1 << N) for _ in range(N)]
# DFS를 통해 순차적으로 최솟값을 찾아 내려간다.
# u는 몇 번째 사람에 대해 일을 할당하고 있는지를 나타낸다.
# visited는 지금까지 어떤 일들을 할당했는지를 나타낸다.
def dfs(u, visited):
    global N
    # 모든 일을 다 배분한 경우
    if visited == (1 << N) - 1:
        return 0
    # 이미 계산했던 entry인 경우
    if dp[u][visited] != -1:
        return dp[u][visited]
    dp[u][visited] = sys.maxsize
    for v in range(N):
        # 해당 일이 할당되지 않은 경우에 dp[u][visited]를 수정한다.
        if (1 << v) & visited == 0:
            dp[u][visited] = min(dp[u][visited], dfs(u+1, visited | (1 << v)) + D[u][v])
    return dp[u][visited]
print(dfs(0, 0))