백준 18235번 지금 만나러 갑니다 (JAVA)

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

18235번: 지금 만나러 갑니다

 

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

처음에는 큐에 두 위치를 한번에 넣어 해결하려고 했습니다. 하지만 메모리 초과가 나오게 됩니다.

그래서 큐에 각각의 위치를 넣고 다른 인덱스로 오리인지 육리인지를 확인하였습니다.

visited boolean 배열을 통해 시간에 따라 오리 또는 육리가 어디에 있을 수 있는지를 파악하고, 오리면 육리가 해당 시간에 해당 지점에 있을 수 있는지, 육리라면 오리가 해당 시간에 있을 수 있는지를 판단하여 결과값을 찾았습니다.

 

package BOJ.bfs;

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

public class BOJ_18235 {
    private static final int NOT_FOUND = -1;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String ,Integer> stoi = Integer::parseInt;
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = stoi.apply(st.nextToken());
        int a = stoi.apply(st.nextToken());
        int b = stoi.apply(st.nextToken());
        int result = bfs(a,b,n);
        System.out.println(result);
    }

    private static int bfs(int a, int b, int n) {
        Queue<int[]> q = new LinkedList<>();
        int time = 0;
        q.offer(new int[]{a,0});
        q.offer(new int[]{b,1});
        boolean[][][] visited = new boolean[n+1][20][2];
        visited[a][time][0] = true;
        visited[b][time][1] = true;
        while(!q.isEmpty()){
            int size = q.size();
            for(int s = 0 ; s < size ; s++){
                int[] now = q.poll();
                if(now[1] == 0 && visited[now[0]][time][1]) {
                    return time;
                }
                if(now[1] == 1 && visited[now[0]][time][0]) {
                    return time;
                }
                int length = (int)Math.pow(2,time);
                int[] next = new int[]{now[0] + length,now[1]};
                if(check(next,n)){
                    visited[next[0]][time+1][next[1]] = true;
                    q.offer(next);
                }
                next = new int[]{now[0] - length,now[1]};
                if(check(next,n)){
                    visited[next[0]][time+1][next[1]] = true;
                    q.offer(next);
                }
            }
            time++;
        }
        return NOT_FOUND;
    }

    private static boolean check(int[] now, int n) {
        if(now[0] >= 1 && now[0] <= n){
            return true;
        }
        return false;
    }
}