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

문제

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

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

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

 

입력

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

출력

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

 

 

문제해결방법 - (서칭 참조)

 

1. 비트마스크를 이용한 dfs탐색으로 재귀함수 끝부분부터 값이 반영되어 최소값을 출력한다.

비트마스크는 이진수 배열을 마치 dfs의 방문리스트처럼 이용한다. 

 

비트마스크의 장점.

1) $O(1)$의 연산속도를 가진다.

2) 적은 메모리를 사용한다.

3) 구현된 코드가 간소함. 

 

컴퓨터의 이진수는 부호와 숫자가 표현되는데, CPU가 데이터를 처리하는 한 번의 단위가 32bit냐, 64bit냐에 따라 이진수가 채워진다. 표현상 이 문제에서는 00000, 00001, 5자릿수까지만 표현하기로 한다.

 

2. (1 << i), (1 >> i) 는 비트의 자릿수를 i에 따라 <<, >>의 방향으로 밀어낸다. 이진수가 밀어지면 결국 아래의 패턴이 된다.

 

1) A << i 식은 A * $2^{i}$과 같다.

00001 이 있고, A = 1, i = 2라면 00100를 출력하고, 00100는 십진수로 4가 된다. (1 * $2^{2}$ = 4)

 

2) A >> i 식은 A / $2^{i}$과 같다.

00100 이 있고, A = 4, i = 2라면 00001을 출력하고, 00001은 십진수로 1이 된다. (1 // $2^{2}$ = 1)

 

3. 위 문제처럼 n = 3 일 때, 00111이 되면 모든 사람이 일을 부여받은 것이다. 이제 dfs로 경우의 수마다 선택하게 되면서 dp[idx][bit]에 선택한 비용의 일을 더한 값 중 최소값이 저장된다. idx가 맨 끝에서부터 거슬러서 올라갈 때 각 분기의 값 중 최소값을 추려서 다시 위로 가져가는 개념이다.(토너먼트를 거쳐서 dp[0][0]에 우승자가 모인다.)

 

십진수	이진수	십진수	이진수	십진수	이진수	십진수	이진수
1	00001	2	00010	3	00011	4	00100
5	00101	6	00110	7	00111	8	01000

 

1) A & B 는 AND연산으로,  대응하는 두 비트가 모두 0, 1일 때, 1을 반환한다. (0이 나오면 지금 도는 비트를 방문하지 않았다는 말임.)

-> 00101 & 00010 = 00000 (0), 00111 & 00010 = 00010 (2)

 

2) A | B 는 OR연산으로, 대응하는 두 비트가 다를 경우, 1을 반환한다. (결국 방문의 합이 되어, 방문을 기록할 수 있음.)

-> 00110 | 00001 = 00111(7), 00101 | 00010 = 00111(7)

 

4. for문에 따라 깊이우선탐색으로 각 경우의 수를 실행하게 되고, 마지막에 dfs(0, 0)에서 각 분기에서 얻은 값들의 최소값을 반영하여 dp[0][0]에 저장하게 된다.

 

5. 최소값을 출력한다.

 

- 코드

import sys
input = sys.stdin.readline

'''
A << B 식은 A * 2의 B제곱과 같다.
A >> B 식은 A / 2의 B제곱과 같다.
00001 = 1 00010 = 2 00011 = 3 00100 = 4 00101 = 5 00110 = 6 00111 = 7
'''

n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]
v = [[-1 for _ in range(1<<n)] for _ in range(n)]

def dfs(idx, bit):
	if idx == n:
		return 0
	if v[idx][bit] != -1:
		return v[idx][bit]
	ans = sys.maxsize
	for i in range(n):
		if (bit & (1 << i)) == 0:
			res = dfs(idx+1, (bit | (1 << i)))
			ans = min(ans, res + d[idx][i])
	v[idx][bit] = ans
	return v[idx][bit]

print(dfs(0, 0))