[백준] 12886번 돌 그룹

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q12886.java

돌맹이 3그룹의 개수를 각 각 준다. 작은 그룹은 큰 그룹에서 돌을 얻어올 수 있다.
예를들어 X그룹보다 Y그룹이 크면 X=X+X로 Y=Y-X로 돌 개수를 변경할 수 있다.
돌 그룹이 모두 동일하게 돌맹이를 분활 할 수 있는지 판단하여 가능시 1 아닐시 0을 출력하여라.

처음 생각

문제를 처음 봤을 때는 별 생각이 없었다가 풀면서 점점 이상해졌던 문제다.

▶ 푼 다음에 보니 index의 문제였다. 이제.. 크기를 벗어나는 idx 뿐만아니라 반복문을 돌릴 때의 변수도 숫자를 잘 확인해야겠다.

다음 생각

BFS 탐색을 통해 풀이를했다. 현재의 그룹 조건에서 제일 작은 그룹과 나머지 두개를 비교해서 조건에 만족한다면 Queue에 넣어주어 다음 탐색을 진행하였다.

▶ Queue에 넣어주기 전에 돌맹이들을 정렬시켜 넣어주었다. 2 1 4 그룹이나 1 2 4 그룹이나 똑같기 때문이다. 이렇게 정렬을 시켜주면 index가 0일 때 값이 가장 작기 때문에 반복문으로 비교할 때도 0인덱스와 나머지를 비교해 주면 되었다.

▶ 이 과정에서 제일 작은 값을 임시로 받아올 때, index를 0이 아닌 그때 그때 index로 지정해놔서 틀린 답이 나왔었다.

다다음 생각

다음으로 문제가 되는것은 중복된 것을 제해줘야한다. 똑같은 돌맹이 그룹을 또 체크할 필요는 없기 때문이다. 예를들어 1 1 2 를 검사했다면, 2 1 1 이 만들어 졌다해도 이는 똑같기 때문에 검사할 필요가없다.

▶ 그룹의 크기를 기준으로 오름차순 정렬을 해놓았기 때문에, 해당 값들을 가지고 문자열을 만들어 HashSet<String>에 넣어주어 중복 관리를 해주었다. 중복된것은 queue에 집어넣지 않는다.

방안

1) Index 관리는 항상 조심하자.

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

package baekjoon.q10000;   import java.util.Arrays; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner;   public class Q12886 {     static int max;     static int[] arr = new int[3];     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int sum = 0;         for(int i=0;i<3;i++) {             arr[i] = sc.nextInt();             sum += arr[i];             max = Math.max(max, arr[i]);         }         // 3개로 쪼갤 수 없다면 볼 필요없다.         if(sum%3!=0) System.out.println(0);         else solve();     }          static HashSet<String> set = new HashSet<>();     private static void solve() {         Queue<Pair> queue = new LinkedList<>();         Arrays.sort(arr);         queue.add(new Pair(arr));         boolean flag = false;         while(!queue.isEmpty()) {             Pair t = queue.poll();             // 모두 동일하다면 종료             if(t.tArr[0]==t.tArr[1]                     &&t.tArr[0]==t.tArr[2]) {                 flag = true;                 break;             }               int next = t.tArr[0];             // 다른 것과 비교(sort되어 있기 때문에 1부터)             for(int i=1;i<3;i++) {                 int[] tArr = new int[3];                 // 원본 복사                 for(int j=0;j<3;j++)                     tArr[j] = t.tArr[j];                 int now = t.tArr[i];                 if(now>next) {                     if(now-next>0) {                         tArr[i] = now-next;                         tArr[t.idx] = next*2;                     }                 }else if(now<next) {                     if(next-now>0) {                         tArr[i] = now*2;                         tArr[t.idx] = next-now;                     }                 }                 // 중복 검사를 막자                 String str="";                 Arrays.sort(tArr);                 for(int j=0;j<3;j++)                     str+=tArr[j];                 if(!set.contains(str)) {                     queue.add(new Pair(tArr));                     set.add(str);                 }             }         }         if(flag) System.out.println(1);         else System.out.println(0);     }          static class Pair{         int[] tArr = new int[3];         int idx;         Pair(int[] t){             for(int i=0;i<3;i++)                 tArr[i] = t[i];         }     } }