<Algorithm> 165.무선충전(SWExpert)

1. 무선충전(SWExpert)

   사용 알고리즘 :  DFS, 완전탐색

• 이문제는 탐색을 어떤 것을 기준으로 하냐에 따라서 상당히 어려울 수 있는 문제다.

• 처음에 접근 방식은 BFS로 BC의 범위에 해당하는 곳에 BC번호를 부여하고 이를 기준으로 비트마스크로 풀려고 했다.

• 비트마스크를 이용하다 보니 속도도 오래 걸리고 Queue 가 계속돌아 메모리도 상당히 커졌다.

• 다른 사람 풀이를 보니 기준을 사람으로 잡고 BC를 완전탐색해서 푼 것을 보고 훨신 쉽구나라는 것을 느꼈다. 

문제에 대한 접근&생각

1. 유저는 최대 2명, BC는 최대 8개 -> 완전탐색!
2. 같은 BC를 사용할 수 있지만 이때는 충전량의 반 -> 결과조건!
3. 원하는 결과가 최대합이므로 유저들을 합쳐서 처리 가능-> sum으로 DFS!

내 코드 

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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125

import java.util.LinkedList; import java.util.List; import java.util.Scanner; import static java.lang.Math.*;   public class Solution {     static int[][] arr;     static int[] move_a;     static int[] move_b;     static int m,a;     static Pair[] user;     static Pair[] bc;     static int[] dx = {0,0,1,0,-1};     static int[] dy = {0,-1,0,1,0};     public static void main(String[] args) {                  Scanner sc = new Scanner(System.in);         int T = sc.nextInt();                  for(int t = 1; t <= T; t++) {             /******************************              * 각 위치마다 2명의 사용자가 bc를 사용하는              * 모든 경우(안쓰는것도 포함)를 DFS를 이용하여              * 탐색한다. 이때 동시에 사용하는 경우는              * 반으로 나눠서 계산하여 처리하여 최대핪을              * 찾아서 각 시간별로 더해서 최댓갑을 구한다.              *******************************/             m = sc.nextInt();// 이동시간             a = sc.nextInt(); // bc 개수             user = new Pair[2];             bc = new Pair[a];              arr = new int[11][11];             move_a = new int[m];             move_b = new int[m];                          for(int i = 0; i < m; i++) {                 move_a[i] = sc.nextInt();             }             for(int i = 0; i < m; i++) {                 move_b[i] = sc.nextInt();             }                          for(int i = 0; i < a ; i++) {                 int x = sc.nextInt();                 int y = sc.nextInt();                 int c = sc.nextInt(); // 충전범위                 int p = sc.nextInt(); // 성능                 bc[i] = new Pair(x, y, c, p);             }             user[0]= new Pair(1, 1, 0, 0);             user[1]= new Pair(10, 10, 0, 0);                          System.out.println("#"+t+" "+solve());         }              }     public static int solve() {         int time = 0;         int total = 0;         int end = m;         while(end-->=0) {             max = 0;             used_bc= new int[a];             charge(0, 0);             total += max;             //System.out.println(max+" 충전량합  "+time+"초");             if(time > m-1) break;             user[0].x += dx[move_a[time]];             user[0].y += dy[move_a[time]];             user[1].x += dx[move_b[time]];             user[1].y += dy[move_b[time]];                          time++;         }         return total;     }     static int[] used_bc;     static int max;     private static void charge(int unum,int sum) {           if(unum == 2) {             for(int i = 0; i < a; i++) {                 if(used_bc[i]==2) sum= sum/2;             }             //System.out.println(sum+" 충전량합");                         max = Math.max(sum, max);             return;         }         for(int i = 0; i < a; i++) {             //System.out.println("user number : "+unum+" bc number : "+i);             if(isRange(bc[i], user[unum])) {                 used_bc[i]++;                 charge(unum+1, sum+bc[i].p);                 used_bc[i]--;             }else {                 charge(unum+1, sum);             }         }     }     private static boolean isRange(Pair bc,Pair user) {         int dist = Math.abs(bc.x-user.x)+Math.abs(bc.y-user.y);         //System.out.println("user : "+user);         //System.out.println("bc : "+bc);         if(dist <= bc.c) return true;         return false;     }          static class Pair{         int x,y,c,p;           @Override         public String toString() {             return "Pair [x=" + x + ", y=" + y + ", c=" + c + ", p=" + p + "]";         }           public Pair(int x, int y, int c, int p) {             super();             this.x = x;             this.y = y;             this.c = c;             this.p = p;         }     } }   Colored by Color Scripter

cs

 

얻은 것

• 탐색 기준을 어떤 것으로 정하느냐에 따라 문제의 수준이 바뀔 수 있음!

• 배열이 아닌 좌표평면으로 나타날경우 x와 y를 반대로 해주면 된다.