백준 비트마스킹 활용 문제풀이
[백준] 1311 할 일 정하기
문제
N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다.
사람은 1번부터 N번까지 번호가 매겨져 있으며, 일도 1번부터 N번까지 번호가 매겨져 있다.
Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람과 일의 수 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 D의 내용이 주어진다. 비용은 10,000보다 작거나 같은 자연수이다.
출력
모든 일을 하는 데 필요한 비용의 최솟값을 출력한다.
문제 접근 방식
- 그리디(현재 상황에서 좋은 것만을 고르는 방법)로 접근할 수 없는 문제였다. 순서대로 좋은 것을 가져왔을때 만약 다른 사람이 그 일을 더 적은 비용으로 할 수 있을 가능성을 무시하게 되기 떄문이다.
- 완전탐색으로도 접근하기에는 아쉬웠다. (a, b)일때 a = 사람 번호, b = 일 번호라고 생각했을 때
(1, 1) - (2, 2) - (3, 4) - (4, 3)과(1, 1) - (2, 2) - (3, 3) - (4, 4)에서(1, 1) - (2, 2)가 같은 경우이고 같은 비용이기 때문에 메모제이션(동일한 계산을 반복 할때 이전에 계산한 값을 메모리에 저장하는 기법)을 활용할 수 있겠다고 생각된다.
int DP[20][1 « 20]
동일한 계산을 반복하는 것을 막기 위해서 DP라는 메모제이션을 위한 전역변수를 선언했다. 이때 크기는 사람의 수 20과 비트마스킹을 활용하여 [1 « 20]의 크기로 선언하였다. 그래서 만약 DP[i][j]일때 i = 사람의 번호, j = 현재 상황에서의 마스킹으로 i번 사람이 이미 맡은 일이 있는지를 비트연산으로 확인 할 수 있다.
int dfs(int index, int mask);
현재 사람들이 맡은 일을 비트로 표현했을 때 mask일때, index ~ 마지막일인 N - 1까지 수행하기 위한 최소비용을 찾기 위한 함수이다.
int& tmp = DP[index][mask];
DP는 전역변수로 선언되어있다. 이때 물론 DP의 일정 값을 재정의 할 수 있긴 하지만 DP[index][mask]를 활용함과 동시에 최솟값으로 갱신해주기 위해서 사용하였다.
mask & (1 « i)
index의 일을 반복문의 변수 i번호의 사람이 할 수 있는지 확인하기 위해서 mask & (1 « i)를 활용하였다.
비트 마스킹 및 비트연산에 관한 설명이 필요하다면 링크를 확인! BitMasking설명
tmp = min(tmp, Cost[i][index] + dfs(index + 1,( mask | (1 « i))));
이전에 레퍼런스로 사용한 tmp에 반복문을 돌면서 tmp와 i번 사람이 index일을 할 때 비용과 dfs(index + 1, (mask | (1 << i)))를 통해서 재귀로 index + 1의 일을 최소로 할 수 있는 사람을 정하는 방식으로 N - 1까지의 최소인 비용을 리턴하도록 한다.
코드
#include <bits/stdc++.h>
using namespace std;
int N;
int DP[20][1 << 20];
int Cost[21][21];
int dfs(int index, int mask){
if(index == N )
return 0;
if(DP[index][mask] != -1)
return DP[index][mask];
int& tmp = DP[index][mask];
tmp = 987654321;
for(int i = 0; i < N; i++){
if((mask & (1 << i)) != 0)
continue;
tmp = min(tmp, Cost[i][index] + dfs(index + 1,( mask | (1 << i))));
}
return tmp;
}
int main(void){
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
cin >> N;
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++)
cin >> Cost[i][j];
}
memset(DP, -1, sizeof(DP));
cout << dfs(0, 0) << "\n";
return 0;
}
백준 1311번 할 일 정하기 풀러가기
댓글남기기