[백준 1311] 할 일 정하기1

백준 1311번 : 할 일 정하기1

www.acmicpc.net/problem/1311

1311번: 할 일 정하기 1

 

---

/* 문제 설명 */

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

Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하여라.

 

/* 해결 방안 */

N명의 사람들과 N개의 일이 있고, 각각의 사람들이 j번 일을 할 때 필요한 비용이 나와있다.

이를 통해 필요한 비용의 최솟값을 구해야하는데 어떻게 해야할까?

 

 

일단 그리디적인 접근은 적합하지 않다.

 

다음과 같은 테스트케이스가 있을 때, 각 사람마다 가장 적은 비용이 드는 일을 선택한다고 가정하자.

3
1 2 3
2 7 9
8 8 8

 

1번 사람이 1번 일을 선택 : 1

2번 사람이 2번 일을 선택 : 7  (1번 일은 이미 앞 사람이 선택했으므로)

3번 사람이 3번 일을 선택 : 8

= 총합 : 16

 

 

하지만 정해는

1번 사람이 2번 일을 선택 : 2

2번 사람이 1번 일을 선택 : 2

3번 사람이 3번 일을 선택 : 8

= 총합 : 12 

이므로, 그리디로는 풀 수 없다는 것을 알 수 있다.

 

 

 

그럼 자연스럽게 완전탐색인가? 라는 생각이 들 것이다.

모든 조합에 대해서 탐색을 해보자.

 

근데 잘 생각해보면 겹치는 것이 있음을 알 수 있다.

1-2-3-4 나 1-2-4-3나, 앞에 있는 1-2는 같기 때문에

이런 겹치는 부분에 대해서는 DP를 사용하여 전에 구한 것을 가져다 쓰도록 하자.

 

 

지금까지 '사람들이 어떤 일을 했는지' 체크하면서 탐색하기 위해서는 비트마스킹을 사용하면 된다.

따라서 DP 식을 작성하자면 아래와 같다.

DP[x][visited] = 현재 x번째 사람을 보고 있고 그 전까지 방문한 조합이 visited 일 때의 최솟값.

 

/* 구현 과정 */

1. 모든 조합에 대해서 탐색할 수 있도록, dfs(int x, int visited) 함수를 수행한다.

2. x는 현재 보고 있는 사람이고, visited은 그 전까지 방문한 조합을 의미함.

3. 이미 방문한 경우(!= -1)는 바로 return 해준다.

4. dp[][]에 최솟값을 계속해서 갱신하며 넣어준다.

 

/* 소스 코드 */

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define WEIGHT 500
typedef long long ll;
typedef pair<int, int>pi;
typedef pair<int, pi>pii;

int n, arr[25][25];
int dp[20][1 << 21];

int dfs(int x, int visited) {
	//모든 사람에 대해 탐색이 완료됨.
	if (visited == (1 << n) - 1) return 0;
    	//이미 방문한 적 있음
	if (dp[x][visited] != -1) return dp[x][visited];

	dp[x][visited] = INF;
	for (int i = 0; i < n; i++)
	{
    		//이미 선택된 애는 넘어감
		if (visited & (1 << i)) continue;
        
        	//dp에 최솟값을 갱신해준다
		dp[x][visited] = min(dp[x][visited], 
			dfs(x + 1, visited | (1 << i)) + arr[x][i]);
	}
	return dp[x][visited];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> arr[i][j];

	memset(dp, -1, sizeof(dp));
	cout << dfs(0, 0);
}

 

/* 얻어갈 점 */

1. 비트마스킹에서, 맨 처음에 배열 사이즈를 초기화 해줄 때 dp[][1 << n] 하면 된다.

2. visited == (1 << n ) - 1 :: 모든 비트 방문 여부확인

3. visited & (1 << k ) :: k번 비트가 1인지 0인지 확인

4. visited |= (1 << k ) :: k번 비트를 1로

3. visited &= ~(1 << k ) :: k번 비트가 0으로 

 

 

 

---