[SWEA] 1865. 동철이의 일 분배

문제

동철이가 차린 전자회사에는 N명의 직원이 있다.

그런데 어느 날 해야할 일이 N개가 생겼다.

동철이는 직원들에게 공평하게 일을 하나씩 배분하려고 한다.

직원들의 번호가 1부터 N까지 매겨져 있고, 해야 할 일에도 번호가 1부터 N까지 매겨져 있을 때, i번 직원이 j번 일을 하면 성공할 확률이 Pi, j이다.

여기서 우리는 동철이가 모든 일이 잘 풀리도록 도와주어야 한다.

직원들에게 해야 할 일을 하나씩 배분하는 방법은 여러 가지다.

우리는 여러 방법 중에서 생길 수 있는 “주어진 일이 모두 성공할 확률”의 최댓값을 구하는 프로그램을 작성해야 한다.

 

풀이방법

DFS(깊이 우선 탐색)알고리즘과 Backtracking(되추적)으로 해결한다.

 

모든 직원이 일이 중복 되지 않도록 일을 선택할 수 있는 모든 경우 중 최대값을 찾는다.

 

1번 직원이 선택할 수 있는 일은 n가지이다.

 

1번 직원이 일을 선택한 후, 2번 직원이 선택할 수 있는 일은 n-1가지이다.

 

2번 직원이 일을 선택한 후, 3번 직원이 선택할 수 있는 일은 n-2가지이다.

 

...

 

n-1번 직원이 일을 선택한 후, n번 직원이 선택할 수 있는 일은 1가지이다.

 

즉, 1부터 n까지 n개의 수가 주어졌을 때, 중복이 허용되지 않는 모든 순열을 구하는 문제이다.

 

순열의 모든 경우의 수는 n개의 숫자가 주여졌을 때, n!이 된다.

 

문제에서 n은 16까지 입력되므로 16!일 경우 시간초과가 발생하게 된다.

 

따라서 백트레킹으로 유망하지 않는 경우는 프루닝해서 탐색하는 노드의 수를 줄인다.

 

프루닝의 조건은 현재 탐색하는 경로에서 i번째 직원(1 <= i <= n)까지의 성공확률이 이전에 구했던 최대 성공확률보다 작을 때이다.

 

확률은 0 ~ 1사이인데, 0 ~ 1 사이의 숫자를 계속 곱하면 계속해서 작아지기만 할 뿐이다.

 

따라서 이미 이전의 최대 성공확률보다 작다면 최대 성공확률이 될 수 없으므로 백트레킹한다.

 

 

소스코드

package samsung;

import java.util.*;

public class s_1865 {
	static double[][] a;
	static int n;
	static double max;
	static int[] visit;
	
	public static void dfs(int x, int depth, double result) {
		result *= a[x][depth];
		visit[x] = 1;
		
		if(depth == n - 1) {
			if(max < result)
				max = result;
			visit[x] = 0;
			return;
		}
		
		for(int i = 0; i < n; i++) {
			if(visit[i] == 0 && result * a[i][depth+1] > max) dfs(i, depth+1, result);
		}
		visit[x] = 0;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int tc = sc.nextInt();
		
		for(int t = 1; t <= tc; t++) {
			n = sc.nextInt();
			a = new double[n][n];
			visit = new int[n];
			max = 0.0;
			
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					a[i][j] = sc.nextDouble() / 100;
				}
			}
			
			for(int i = 0; i < n; i++) {
				dfs(i, 0, 1);
			}
			System.out.printf("#%d %.6f\n", t, max*100);
		}
	}
}