백준 12886번 돌 그룹 (JAVA)

https://www.acmicpc.net/problem/12886

12886번: 돌 그룹

 

저는 BFS를 통해 문제를 해결하였습니다.

방문 체크는 Set<String>을 통해 하였습니다.

배열을 한번 정렬 후 Set에 Arrays.toString(arr)이 있는지를 판단하여 있다면 방문했다고 판단하고, 없다면 set에 넣고 BFS를 진행하였습니다.

배열의 값이 모두 같다면 SUCCESS를 리턴하여 끝내고 방문할 수 있는 것을 모두 방문했는데도 안된다면 FAIL을 리턴하여 풀었습니다.

 

package BOJ.bfs;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_12886 {
    private static final int SIZE = 3;
    private static final int SUCCESS = 1;
    private static final int FAIL = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Function<String,Integer> stoi = Integer::parseInt;
        int[] num = new int[SIZE];
        for(int i = 0 ; i < SIZE ; i++){
            num[i] = stoi.apply(st.nextToken());
        }
        int result = bfs(num);
        System.out.println(result);
    }
    private static int bfs(int[] num) {
        Queue<int[]> q = new LinkedList<>();
        Arrays.sort(num);
        q.offer(num);
        Set<String> visited = new HashSet<>();
        while(!q.isEmpty()){
            int[] now = q.poll();
            if(now[0] == now[1] && now[1] == now[2]){
                return SUCCESS;
            }
            for(int i = 0 ; i < 3 ; i++){
                int[] next = Arrays.copyOf(now,now.length);
                int j = (i + 1) % 3;
                int min = Math.min(next[i],next[j]);
                int max = Math.max(next[i],next[j]);
                if(max == min){
                    continue;
                }
                next[i] = max - min;
                next[j] = 2 * min;
                Arrays.sort(next);
                if(!visited.contains(Arrays.toString(next))){
                    visited.add(Arrays.toString(next));
                    q.offer(next);
                }
            }

        }
        return FAIL;

    }
}