[SW Expert] 5644. [모의 SW 역량테스트] 무선 충전

생각

무선 충전기가 여러곳에 설치되어있다. 각각의 충전기는 각자의 파워와 범위를 가지고 있다.
사람 A,B 두명이 각 각 (1,1) (10,10)에서 출발하여 M 만큼의 방향 명령에 따라서 이동을 한다.
이 때, 한 충전 범위에 두명이 들어있다면 해당 충전 파워/2 만큼 충전을 할 수 있다.
같은 충전기의 범위에 2명이 들어있다해도, 1명이 다른 충전기를 사용하면 다른 한 명이 온전히 충전기를
사용할 수 있다.
A 대의 무선 충전기의 위치와 파워 범위가 주어지고, A,B의 이동 현황이 주어질 때 최대 충전 파워를 구하시오.

처음 생각

A와 B가 이동 할 때마다 각각의 충전기와 거리를 계산해 범위에 들어가는 확인하는 것은 비효율 적이라 생각하여, 미리 맵 배열에 충전기의 범위 만큼 리스트에 들어있는 각 충전기의 인덱스를 깔아놓았다.

▶ 인덱스를 미리 깔아놓으면서 겹치는 충전 범위가 있다면 예를들어 1번과 2번이 겹친다면 102로 표시하여 후에 사용할 때는 0을 기준으로 나누어서 인덱스를 얻었다. int 형으로 만들 시에 최대 8개 이므로 102030405060708 이되어 int 범위를 넘어서서 String 형으로 배열을 만들어 주었다.

▶ 다른 분의 후기를 보니 2진수를 사용하여 구별을 해주는 간단한 방법도 있었다.

▶ 초기 x,y를 메소드로 넘겨주고 나서 초기 index를 바로 arr[x][y] = idx로 작성했었는데 이게 문제가 되었었다. 다른 충전기의 흔적을 지워버렸던 것이다. 이 오류를 찾느냐고 시간을 많이 썻다.

다음 생각

사람을 2명을 이동시켜야하는데 Queue 에 담아 한 명씩 이동시킨 후, 계산을 하는 것이 어려워 둘을 꺼내어서 한 번에 둘 씩 진행을 시킨 후 계산하는 형식을 취하였다.

다다음 생각

이동할 때마다 그 위치에 따른 각각 사용가능한 충전기의 Index를 얻을 수 있으므로, 이를 얻어 이중 반복문을 통해 완전탐색을 통하여 최대값을 구해 return해 주었다.

방안

1) 오류를 사전에 방지하기 위해서 시간이 조금 더 걸리더라도 천천히 풀기

2) 계산이 맞다는 생각이 드는데 오류가 난다면 배열을 항상 확인하기

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 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.StringTokenizer;   class Solution {     static int m,a;     static int[][] p;     static String[][] arr;     static List<Pair> list = new ArrayList<>();     static int[] check;     public static void main(String[] args) throws IOException{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         int tc = Integer.parseInt(br.readLine());         StringBuilder sb = new StringBuilder();         for(int i=1;i<=tc;i++) {             StringTokenizer st = new StringTokenizer(br.readLine());             list.clear();             arr = new String[10][10];             for(int j=0;j<10;j++)                 Arrays.fill(arr[j], "0");             m = Integer.parseInt(st.nextToken()); // 이동수             a = Integer.parseInt(st.nextToken()); // bc의 개수             // 충전기 방문 체크             check = new int[a+1];             p = new int[2][m];             // 사람 입력 받기             for(int j=0;j<2;j++) {                 st = new StringTokenizer(br.readLine());                 for(int k=0;k<m;k++)                     p[j][k] = Integer.parseInt(st.nextToken());             }                          // idx를 1부터 사용하기 위해서             list.add(new Pair(0, 0, 0, 0));             // ap 정보 받기 & 맵에 미리 펼치기             for(int j=0;j<a;j++) {                 st = new StringTokenizer(br.readLine());                 int x = Integer.parseInt(st.nextToken());                 int y = Integer.parseInt(st.nextToken());                 int c = Integer.parseInt(st.nextToken());                 int p = Integer.parseInt(st.nextToken());                 list.add(new Pair(y-1,x-1,c,p));                 charge(y-1,x-1,c,p,j+1);             }             sb.append("#"+i+" "+solve()+"\n");         }         System.out.print(sb);     }          // 맵에 미리 범위 미리 넣어놓기.     static int[][] dir = {{1,0},{0,1},{-1,0},{0,-1}};     private static void charge(int x,int y,int c,int p,int idx) {         Queue<Pair> queue = new LinkedList<>();         queue.add(new Pair(x, y, 0, idx));         boolean[][] visited = new boolean[10][10];         if(arr[x][y]!="0")             arr[x][y] = arr[x][y]+"0"+idx;         else arr[x][y] = idx+"";         visited[x][y] = true;         while(!queue.isEmpty()) {             Pair t = queue.poll();             if(t.c==c) continue;             for(int i=0;i<4;i++) {                 int tx = t.x+dir[i][0];                 int ty = t.y+dir[i][1];                 if(tx<0 || ty<0 || tx==10 || ty==10) continue;                 if(visited[tx][ty]) continue;                 visited[tx][ty] = true;                 if(arr[tx][ty]!="0") {                     arr[tx][ty] = arr[tx][ty]+"0"+idx;                 }else arr[tx][ty] = idx+"";                 queue.add(new Pair(tx, ty, t.c+1, t.p));             }         }     }          private static int solve() {         Queue<Person> queue = new LinkedList<>();         queue.add(new Person(0, 0, 0, 0));         queue.add(new Person(9, 9, 1, 0));         int result = 0;         while(!queue.isEmpty()) {             Person t = queue.poll();             Person t2 = queue.poll();             int tx = t.x,ty = t.y;             int tx2 = t2.x, ty2 = t2.y;             // 모든 경우수를 따져서 파워구하기             result += power(tx,ty,tx2,ty2);                          // 시간이 끝나면 다 더해주기             if(t.time==m) break;                          // 다음 칸으로 가기             switch (p[t.n][t.time]) {             case 1: tx-=1;break;             case 2: ty+=1;break;             case 3: tx+=1;break;             case 4: ty-=1;break;             }             switch (p[t2.n][t2.time]) {             case 1: tx2-=1;break;             case 2: ty2+=1;break;             case 3: tx2+=1;break;             case 4: ty2-=1;break;             }             queue.add(new Person(tx, ty, t.n, t.time+1));             queue.add(new Person(tx2, ty2, t2.n, t2.time+1));         }         return result;     }          // 가장 큰 파워 찾기     private static int power(int x,int y,int x2,int y2) {         // 0으로 초기화         int[] tArr = {0},tArr2 = {0};         // 1의 경우의 수 가져오기         if(arr[x][y].length()>=3) {             StringTokenizer st = new StringTokenizer(arr[x][y],"0");             int cnt = st.countTokens();             tArr = new int[cnt];             for(int i=0;i<cnt;i++)                 tArr[i] = Integer.parseInt(st.nextToken());         }else if(!arr[x][y].equals("0")) {             // 전기를 1개만 공급 받을 수 있다면             tArr[0] = Integer.parseInt(arr[x][y]);         }         // 2의 경우의 수 가져오기         if(arr[x2][y2].length()>=3) {             StringTokenizer st = new StringTokenizer(arr[x2][y2],"0");             int cnt = st.countTokens();             tArr2 = new int[cnt];             for(int i=0;i<cnt;i++)                 tArr2[i] = Integer.parseInt(st.nextToken());         }else if(!arr[x2][y2].equals("0")) {             tArr2[0] = Integer.parseInt(arr[x2][y2]);         }         int max = 0;         for(int i=0;i<tArr.length;i++) {             for(int j=0;j<tArr2.length;j++) {                 max = Math.max(max, getMax(tArr[i],tArr2[j]));             }         }         return max;     }          private static int getMax(int idx1,int idx2) {         // index가 같다면 같은 충전기에 있는 것이므로 *2 니깐 그대로         if(idx1==idx2) return list.get(idx1).p;         else return list.get(idx1).p+list.get(idx2).p;     }          static class Person{         private int x,y,n,time;         public Person(int x,int y,int n,int time) {             this.x = x;             this.y = y;             this.n = n;             this.time = time;         }     }     static class Pair{         private int x,y,c,p;         public Pair(int x,int y,int c,int p) {             this.x = x;             this.y = y;             this.c = c;             this.p = p;         }     } } Colored by Color Scripter

cs