백준 17071 자바 - 숨바꼭질 5 문제

www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

 

숨바꼭질 5에서는 동생이 움직이며 범위가 50만으로 증가한 조건이 주어집니다.

동생이 움직이기때문에 동일한 시간에 동일한 위치에 있어야만 합니다. 

 

숨바꼭질 문제로 풀게 될 경우

수빈 : 3 → 6 → 12

동생 : 6 → 7 → 9 → 12

 

수빈은 2초에 12자리에 가서 방문처리를 하게되면

동생이 3초에 12에 도달하면서 12의 방문처리가 되어 있기 때문에 3초를 반환하게 되는데

문제의 조건에 의해 2초 때 12 위치에서 3초 때 12 위치로 이동할 방법이 없으므로 틀리게 됩니다.

 

 수빈이 t 초에서 위치가 p라고 가정할 때, t + 1초에서 위치는 p일 수 없습니다. 하지만 t + 2초에서는 위치가 p일 수 있습니다(t → t – 1 → t 혹은 t → t + 1 → t).

한번 방문했던 곳을 2초가 있으면 다시 방문할수있게 됩니다. 수빈이 동생을 순간이동을 앞질러서 동생이 도착할 곳에 먼저 도착하고 그자리를 2초 간격으로 유지할수 있다는것을 의미합니다.

수빈이 p위치에 도착하는 t초가 짝수이면 짝수 시간때 마다 p위치로 돌아올수 있고

p위치에 도착하는 t초가 홀수이면 홀수 시간때마다 p위치로 돌아올수 있습니다. 

이를 바탕으로 방문을 2차원 배열로 홀수와 짝수를 계산 할수 있게 하여 해결하였습니다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 숨바꼭질5 문제 - 17071번
public class HideAndSeek5 {

    static int N, K;
    static boolean[][] visited = new boolean[500001][2];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        if(N == K){
            System.out.println(0);
        }else {
            System.out.println(bfs(N));
        }
    }

    static int bfs(int start) {
        int time = 0;
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start][time] = true;

        while (!q.isEmpty()) {
            // K가 범위를 벗어나는 경우
            if(K > 500000) {
                return -1;
            }

            // time 의 짝수 홀수
            int newTime = time % 2;

            // 만난 경우(짝수, 홀수)
            if(visited[K][newTime]) {
                return time;
            }

            // 현재 q의 사이즈 만큼만 돌리기 - 시간 계산을 위해서
            for(int j = 0, size = q.size(); j < size; j++) {
                int now = q.poll();
                // 다음 이동의 짝수 홀수 여부
                int nextTime = (time + 1) % 2;
                int next;

                // 다음에서 영역을 방문 처리
                next = now - 1;
                if(next >= 0 && !visited[next][nextTime]) {
                    visited[next][nextTime] = true;
                    q.offer(next);
                }

                next = now + 1;
                if(next < 500001 && !visited[next][nextTime]) {
                    visited[next][nextTime] = true;
                    q.offer(next);
                }

                next = now * 2;
                if(next < 500001 && !visited[next][nextTime]) {
                    visited[next][nextTime] = true;
                    q.offer(next);
                }
            }
            time++;
            K += time;
        }
        return -1;
    }
}