알고리즘 풀이/DFS(깊이 우선 탐색)
SWEA 2112 [보호 필름]
갓우태
2018. 9. 25. 19:25
SW Expert Academy 보호 필름 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu&categoryId=AV5V1SYKAaUDFAWu&categoryType=CODE
//SWEA는 문제를 무단으로 복제하는 것을 금지하기에, 자세하게 설명하지 않습니다.
성능검사를 하기 위해 필요한, 최소한의 약품 투입 횟수를 구하는 문제입니다.
해결방법은 다음과 같습니다.
1. 각 투입횟수마다 나올 수 있는 경우를 저장.
-> A : 0, B : 1로 둔 뒤, 투입 횟수가 1회 : A : [0], B : [1]
투입 횟수가 2회 : AA : [0 , 0], AB : [0, 1] , BA : [1, 0], BB : [1, 1]...
이런식으로 이진수를 통해 저장
2. 나올 수 있는 투약방법마다 DFS를 통해 인덱스의 조합을 고른다.
-> 1회 : (0) , (1), (2) , (3), (4), (5). ..
->2회 : (0, 1), (0, 2), (0, 3) ... ... (1, 2), (1, 3) .... ( 4, 5)
3. 인덱스를 고를 때 마다, 해당 인덱스에 해당 약품투약을 해준다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | import java.util.*; public class Solution { public static int T, D, W, K; public static int[][] Map = new int[13][20]; public static int[] arr = new int[13]; //이진수 저장 public static boolean is_end; public static int Result = 0; public static boolean is_pass() { for(int j = 0; j < W; j++) { boolean line = false; for(int i = 0; i <= D - K; i++) { int num = 1; for(int k = 1; k < K; k++) { if(Map[i + k][j] == Map[i][j]) num++; } if(num == K) { line = true; break; } } if(!line) return false; } is_end = true; return true; } public static void DFS(int size, int index, int capacity) { if(size == capacity) { if(is_pass()) { Result = capacity; return; } } for(int i = index; i < D; i++) { int[] temp = new int[W]; for(int j = 0; j < W; j++) { temp[j] = Map[i][j]; Map[i][j] = arr[size]; } DFS(size + 1, i + 1, capacity); for(int j = 0; j < W; j++) Map[i][j] = temp[j]; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); T = sc.nextInt(); for(int t= 1; t<= T; t++) { D = sc.nextInt(); W = sc.nextInt(); K = sc.nextInt(); Result = 0; is_end = false; for(int i = 0; i < D; i++) { for(int j = 0; j < W; j++) { Map[i][j] = sc.nextInt(); } } for(int i = 0; i <= D; i++) { if(i == 0) { is_pass(); } else { for(int j =0; j < (int)Math.pow(2, i); j++) { int num = j; for(int k = i-1; k >= 0; k--) { arr[k] = num%2; num /= 2; } DFS(0, 0, i); if(is_end) break; } if(is_end)break; } if(is_end)break; } System.out.println("#" + t + " " + Result); } } } | cs |
반응형