[백준] 1697번 : 숨바꼭질 - JAVA [자바]

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

bfs 알고리즘 문제이다.

1. 수빈이의 위치 N 에서 시작한다.
2. N-1, N+1, 2xN 의 위치를 갈 수 있는지 보고 갈 수 있다면 현재 위치(N)에서 1초 후라는 의미로 현재 시간에서 + 1 초 해준다.
3. 이동한 위치를 큐에 삽입하고 방문 처리 해준다.
4. 그 위치에서 또 N-1, N+1, 2xN의 위치를 탐색한다.
5. 방문을 안한 위치면 반복하여 시간을 입력한다.
6. 방문을 이미 한 위치이면
   6.1 현재 방법의 시간과 비교하여 더 적은 시간으로 업데이트 하고 큐에 삽입한다.
   6.2 현재 방법이 더 느리다면 더 탐색하지 않기 위해 큐에 삽입하지 않고 건너뛴다.
7. 배열에서 동생의 위치의 값을 출력한다.

public class bj1697 {

    public static int N, K;
    public static boolean[] visited = new boolean[100001];
    public static int[] answer = new int[100001];
    public static Queue<Integer> queue = new LinkedList<>();
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line = br.readLine();
        String[] split = line.split(" ");

        N = Integer.parseInt(split[0]);
        K = Integer.parseInt(split[1]);

        bfs(N);

        bw.write(answer[K] + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    public static void bfs(int start) {
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            start = queue.poll();
            visited[start] = true;
            int moveLeft = start - 1;
            int moveRight = start + 1;
            int teleport = start * 2;
            if (teleport <= 100000) {
                // 방문 안했으면 값 업데이트
                if (!visited[teleport]) {
                    queue.add(teleport);
                    answer[teleport] = answer[start] + 1;
                    visited[teleport] = true;
                } else {
                    // 방문했었지만
                    // 지금 방법이 더 빠른 경우
                    if (answer[teleport] > answer[start] + 1) {
                        queue.add(teleport);
                        answer[teleport] = answer[start] + 1;
                    }
                }
            }
            if (moveLeft >= 0){
                // 방문 안했으면 값 업데이트
                if (!visited[moveLeft]) {
                    queue.add(moveLeft);
                    answer[moveLeft] = answer[start] + 1;
                    visited[moveLeft] = true;
                } else {
                    // 지금 방법이 더 빠른 경우
                    if (answer[moveLeft] > answer[start] + 1) {
                        queue.add(moveLeft);
                        answer[moveLeft] = answer[start] + 1;
                    }
                }
            }
            if (moveRight <= 100000) {
                // 방문 안했으면 값 업데이트
                if (!visited[moveRight]) {
                    queue.add(moveRight);
                    answer[moveRight] = answer[start] + 1;
                    visited[moveRight] = true;
                } else {
                    // 지금 방법이 더 빠른 경우
                    if (answer[moveRight] > answer[start] + 1) {
                        queue.add(moveRight);
                        answer[moveRight] = answer[start] + 1;
                    }
                }
            }
        }
    }

}