[백준/Python]1311: 할 일 정하기 1

문제

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

백준 단계별로 풀어보기 - 동적 계획법 3

---

풀이

N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다.
사람은 1번부터 N번까지 번호가 매겨져 있으며, 일도 1번부터 N번까지 번호가 매겨져 있다.
Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

 

동적 계획법 3 문제는 모두 비트마스킹을 통해 풀어야 한다.

 

예시 입력값대로 N = 3이라고 가정해보자.

우리는 3개의 비트를 사용하여 일의 진행 상황을 나타내야 한다.

000 => 아무 일도 선택되지 않은 상황

001 => 첫번째 일만 배정된 상황

101 => 첫번째, 세번째 일이 배정된 상황

즉, 가능한 경우의 수는 1 << 3 = 2^3 = 8 이다. (000~111)

 

dp에는 모든 상태에서 일을 배정하는데 드는 최소 비용을 저장한다.

따라서 dp = [엄청큰값] * (1 << 3) 으로 초기화 한 뒤 진행한다.

 

그 다음 반복문을 통해, 현재 어떤 사람이 일을 맡을 차례인지 & 어떤 일이 남아있는지 를 판단한다.

만약 현재 일을 맡을 수 있는 상황이라면, dp[현재 일을 맡았을때의 비트값] = min(기존 dp값, 일을 맡지 않았을때의 dp값 + 현재 일의 비용)으로 더 작은값으로 갱신한다.

 

참고로 나는 반복문을 통해 풀었는데, 재귀함수로 풀어야 Python3로 통과할 수 있다.

(또는 헝가리안 알고리즘을 사용해야 한다. 이 알고리즘은 나중에 공부해봐야할듯...)

 

아래는 PyPy3로 통과한 코드다.

# (PyPy3) 메모리: 118788KB / 시간: 820ms
from sys import stdin


input = stdin.readline
INF = int(1e9)

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

dp = [INF] * (1 << N)  # 경우의 수가 000~111까지 8개이므로 1 << 3 => 8
dp[0] = 0

for i in range(1 << N):
    x = bin(i).count("1")

    for j in range(N):
        if not (i & (1 << j)):  # 이미 선택된 일이 아니라면
            nxt = i | (1 << j)
            dp[nxt] = min(dp[nxt], dp[i] + D[x][j])

print(dp[(1 << N) - 1])

 

예를들어 i가 6이면 110이고, x는 2가 된다.

넘어가서 j가 0일때 1 << 0 = 001 이므로 110 & 001 = 0 이 돼서 조건문을 통과한다.

nxt = 110 | 001 = 111 = 7

dp[7(111)] = min(dp[7(111)], dp[6(110)] + D[2][0]) 으로 최소비용을 갱신하는 방식이다.

(D[2][0] = 3번째 사람이 1번째 일을 할 때의 비용)

---

아래는 Python3로 통과한 분의 코드다.

반복문이냐 재귀냐의 차이인듯 싶다.

출처👉 https://ji-gwang.tistory.com/446

# 아래는 Python3로 통과되는 코드다. 재귀를 사용.
# 출처: https://ji-gwang.tistory.com/446
# 메모리: 72080KB / 시간: 4796ms
import sys

input = sys.stdin.readline


def dfs(row, visit):
    if row == N:
        return 0

    if visited[visit] != -1:
        return visited[visit]

    ret = 1000000000
    for i in range(N):
        if (visit & (1 << i)) != 0:  # 특정 비트가 켜저있다면
            continue

        ret = min(ret, dfs(row + 1, (visit | (1 << i))) + tasks[row][i])

    visited[visit] = ret

    return visited[visit]


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

visited = [-1] * (1 << N)
print(dfs(0, 0))

각 row(사람 순서)대로 최소 비용을 선택하는 방식이다. i가 row, dp가 visited, j가 i로 바뀐 상태라고 보면 된다.

해당 사람이 N개의 일 중 하나를 맡을 경우를 체크한다.

ret은 현재 일이 아닌 이전 일을 선택했을때의 경우의 값(처음엔 엄청큰값)을 나타내고,

dfs(다음 사람, 현재 일을 선택했을 경우의 최종값)과 비교해 더 적은 값으로 갱신한다.

 

그리고 dfs()를 통해 체크한 해당 경우의 값이 이미 존재한다면, 다시 체크하지 않고 바로 기존값을 반환해준다.

여기서도 효율 차이가 났던것같다.

---

마지막으로 헝가리안 알고리즘을 사용한 방식이다.

실행시간 차이가 말도안된다ㅋㅋㅋ 오마이깟

# 실행시간 48ms인 코드. Hungarian 알고리즘을 사용함.
from sys import stdin
from itertools import product

input = stdin.readline

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


def hungarian(table):
    N = len(table)
    match_x, match_y = [None] * N, [None] * N
    label_x, label_y = list(map(max, table)), [0] * N
    is_free_x, is_free_y = (lambda x: match_x[x] == None), (
        lambda y: match_y[y] == None
    )
    gap = lambda i, j: label_x[i] + label_y[j] - table[i][j]

    while None in match_x:
        tree_x, tree_y = [None] * N, [None] * N
        S, T = [False] * N, [False] * N

        u = next(filter(is_free_x, range(N)))
        S[u] = True
        slack, slack_x = [gap(u, j) for j in range(N)], [u] * N

        while True:
            try:
                y = next(filter(lambda j: (slack[j] == 0) and (not T[j]), range(N)))

            except:
                min_gap = min(v for v, b in zip(slack, T) if not b)
                for i in range(N):
                    label_x[i] -= min_gap * int(S[i])
                    label_y[i] += min_gap * int(T[i])
                    slack[i] -= min_gap * int(not T[i])

            else:
                if is_free_y(y):
                    tree_y[y] = slack_x[y]
                    while y != None:
                        x = tree_y[y]
                        match_y[y], match_x[x], y = x, y, match_x[x]
                    break

                else:
                    z = match_y[y]
                    tree_x[z], tree_y[y] = y, slack_x[y]
                    S[z], T[y] = True, True
                    for i in range(N):
                        slack[i], slack_x[i] = min(
                            (gap(z, i), z), (slack[i], slack_x[i])
                        )

    return list(enumerate(match_x)), sum(label_x) + sum(label_y)


for i, j in product(range(N), repeat=2):
    table[i][j] *= -1

_, ans = hungarian(table)

print(-ans)

 

처음 들어보는 알고리즘이라서 좀 공부해야될듯하다.