[BOJ] 1311 할일 정하기 1 (Python3)

문제

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

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

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

입력

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

출력

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

정답코드

n = int(input())
workSheet = [list(map(int, input().split())) for _ in range(n)]
INF = 987654321
dp = [[INF for _ in range(1 << n)] for i in range(20)]

def dfs(cnt, visit):
    if visit == (1 << n) - 1:
        return 0
    
    if dp[cnt][visit] != INF:
        return dp[cnt][visit]
    
    for i in range(n):
        bit = 1 << i
        
        if visit & bit:
            continue
            
        dp[cnt][visit] = min(dfs(cnt + 1, visit | bit) + workSheet[cnt][i], dp[cnt][visit])
        
    return dp[cnt][visit]

print(dfs(0,0))

문제 풀이

dfs + dp 문제 같으면서도 아무리 해도 DP로 시간초과를 통과 할 수 없었다. 우선 무조건 순열의 경우의 수를 구해야 하기 때문에 최대 20명의 순열을 찾으려면 20!로 dfs로는 시간초과를 통과할 수 없다. 그렇다고 해서 dfs의 재귀를 줄일 수 있는 조건이 존재하는 것 같지도 않았다.

그래서 풀이를 찾아보니 비트마스킹 문제라는 것을 알게 되었다.

사실 백준에서 풀다보면 여러 억까 알고리즘을 만나게 되는데, 비트 마스킹 정도는 실제 코테에서도 자주 출제 되고, 경우의 수를 비트 마스킹 하여 풀면 여러모로 실전에 도움이 될 것 같아서 공부해보았다.

비트 마스킹은 말그대로 우리가 원하는 결과를 비트연산을 통해 시간 복잡도를 줄이는 방법이다.

위의 문제에서도 보면 예제가 n = 3으로 되어있는데, 3명이 일을 안맡은 상태면 0, 맡은 상태면 1로 표시하면 된다.

예를들어, 첫번째 사람이 일을 맡고 나머지는 아직 맡지 않았다면, 100이고, 두번째 사람이 일을 맡았다면 010, 세번째 사람이 일을 맡았다면 001이다. 이 경우의 수를 따져보면 결국 (1 « n)과 같음을 알 수 있다.

중간에 & 과

연산자가 있는데, 간단히 생각하면 &연산자는 이미 마킹된 1을 찾는 것이고

는 아직 0인 곳에 1로 마킹해주는 것이다.

예를들어 001 & 001이라면 1이 이미 마킹 되어있으므로 continue를 이용해 패스해주고, 000

001 이라면 아직 1이 마킹이 되어 있지 않으므로 001로 마킹해주는 역할을 하게된다.

따라서 평소에 자주 풀었던 dp + dfs문제를 비트 마스킹을 이용하여 메모이제이션해주며 문제를 풀면 된다.