문제

숨바꼭질 3

풀이

순간이동은 0초후 2*x, 1초후는 x-1, x+1 의 위치에 있을수 있는데,
형이 동생의 위치로 갈 가장 빠른 초를 구하는 방법이다. 모든 경우의 수를 전부 가는데 위치가 0초후 갈수 있는 곳이 생기기 때문에 deque로 현재 위치를담고 addLast addFirst 를 사용해서 큐 위치를 바꿔주는 형식으로 사용하면 된다

1. 자료형 선언

	public static int[] dist = new int[MAX]; // 인덱스 위치에 가기 위해 간 횟수
    public static boolean[] check = new boolean[MAX]; // 방문 여부
    public static Deque<Integer> d = new LinkedList<>(); // 현재 위치 담는 덱

• 인덱스에 가기 위한 가장 짧은 이동 횟수를 담는 dist
• 인덱스에 방문 한 여부를 담는 check
• 현재 위치 를 담는 deque

2. 다음 위치로 이동하기 위한 메서드 생성

	private static void condition(int next, int current) {
        if (next < MAX && next >= 0) {
            if (!check[next]) {
                check[next] = true;
                dist[next] = dist[current] + 1;
                d.addLast(next);
            }
        }
    }

    private static void condition2(int next, int current) {
        if (next < MAX && next >= 0) {
            if (!check[next]) {
                check[next] = true;
                dist[next] = dist[current];
                d.addFirst(next);
            }
        }
    }

• condition2 는 0초후 이동할때 사용할 함수이고 condition은 1초후 이동할때 다음 위치를 담는 함수이다

전체 코드

전체 코드