c언어 1311번 할 일 정하기 1 (백준)

#include<stdio.h>
#define MAX 1e9
int n,arr[20][20],dp[20][1<<20]={};

int dfs(int level, int visited) {
	if(level == n) return 0; //모두 방문
	if(dp[level][visited]) return dp[level][visited]; //이미 탐색함 
	dp[level][visited] = MAX; //최솟값을 구하기 위해 일단 범위 초과값 대입 
	for(int i=0; i<n; i++) {
		if(!(visited & 1<<i)) { //이전에 방문하지 않음 
			int tmp = arr[level][i] + dfs(level+1, visited | 1<<i);  
			dp[level][visited] = dp[level][visited]<tmp?dp[level][visited]:tmp; //기존값보다 더 작으면 변경 
		} 
	}
	return dp[level][visited];
}

int main(void) {
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	 for(int j=0;j<n;j++)
	  scanf("%d",&arr[i][j]);
	
	printf("%d",dfs(0,0));
}

 

풀이 : 비트필드를 이용한 다이나믹 프로그래밍

 

그리드론 풀 수 없지만, 브루트포스로 풀기엔 시간이 너무 많이 걸립니다. 그래서 다이나믹 프로그래밍으로 완전 탐색을 합니다. 여기서 방문처리를 하기위해 비트필드를 이용합니다. 

 

n <= 20 이므로 int (4byte) 변수에 1비트씩 자리를 할당 한다면 방문 처리를 할 수 있습니다.

 

ex) n = 6,      0, 2, 4 번 방문 ->  010101 으로  구성하면 됩니다.

---

 

위의 코드는 다이나믹 프로그래밍을 dfs 로 구현한 코드 입니다. (방문처리는 비트필드로)

 

다이나믹 프로그래밍 이므로 이미 부분적으로 값을 구한 곳은 dp 값만 불러오면 됩니다. 그렇지 않으면 브루트포스와 다를게 없습니다.

 

(재활용이 되는 예,  사람 5명, 1-4-2-3-5, 4-1-2-3-5 이렇게 2가지의 탐색 순서가 있을 때, 1-4-2-3-5 에서 얻은 dp[3][10110], 을 4-1-2-3-5 에서 다시 활용할 수 있습니다)

 

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